2024 - 08- 26 C++ 코딩테스트 10주완성 D+33

백준 2589 문제 - 보물섬

 

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다.

 

보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다.

 

각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다.

 

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.

 

육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

 

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

 

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다.

이어 각각의 원소 L 또는 W 를 입력받는다. ( L은 땅, W는 바다를 의미하고, 각 행마다 띄워쓰기는 하지않는다.)

보물 지도의 가로, 세로의 크기는 각각 50이하이다.

 

출력

 

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//1. 변수목록
//맵의 최대 크기를 정의할 정수형 변수 int max_length = 54;
//맵의 행과 열의 크기를 받을 정수형 변수 int n,m;
//맵을 표현할 2차원 문자열 배열 a[max_length][max_length];
//최단거리를 비교할 땅을 담을 벡터 vector<pair<int>> land;
//방문한 곳을 표현할 2차원 정수 배열 visited[max_length][max_length]
//각 땅마다의 최단거리를 정의할 정수형 변수 min_distance
//땅마다 비교하여 최대의 거리를 저장할 정수형 변수 max_distance,ret
//땅마다의 바다의 개수를 비교하기 위한 
//dy[4] = {-1,0,1,0}
//dx[4] = {0,1,0,-1}
const int max_length = 54;
int n, m, min_distance, ret;
int a[max_length][max_length],visited[max_length][max_length];
vector<int> max_distance;
vector<pair<int,int>> land;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1 , 0 , -1 };

//2-3-2. void dfs(int starty,int startx,int ary,int arx);
	//2-3-2-1. visited[y][x] = 1;
	//2-3-2-2. 4까지 반복문	
	//2-3-2-2-1. int ny = y + dy[i];
	//2-3-2-2-2. int nx = x + dx[i];
	//2-3-2-2-3. if(ny < 0 || ny >= n || nx < 0 || nx >= m)
	//2-3-2-2-3-1 continue;
	//2-3-2-2-4. if(!visited[ny][nx] && a[ny][nx] == 'L')
	//2-3-2-2-4-1. min_distance++;
	//2-3-2-2-4-2. dfs(ny,nx,ary,arx);
	//2-3-2-2-4-3. if(min_distance < max _distance) max_distance = min_distance;
	//2-3-2-2-4-4. min_distance = 0;
	//2-3-2-2. 4까지 반복문 종료
	//2-3-2. dfs(int starty,int startx,int ary,int arx) 함수 설명 종료
void dfs(int y, int x, int ary, int arx)
{
	visited[y][x] = 1;

	if (y == ary && x == arx)
	{
		max_distance.push_back(min_distance);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || ny >= n || nx < 0 || nx >= m)
			continue;

		if (!visited[ny][nx] && a[ny][nx] == 'L')
		{
			min_distance++;
			dfs(ny, nx, ary, arx);			
		}
	}
	
	
	return;
}



int main()
{
	//2. 알고리즘
	//2-1. 보물섬 지도의 열과 행을 입력받는다.
	cin >> n >> m;
	//2-1-1 max_distance = n * m
	ret = n * m;
	//2-2. 보물섬 지도의 열의 길이만큼 반복문
	//2-2-1. 임시 문자열 str을 선언하고 입력받는다.
	//2-2-2. 보물섬 지도의 행만큼 반복문
	//2-2-2-1. a[i][j] =str[j]
	//2-2-2-1. int cnt = 0;
	//2-2-2-2. i=0 부터 4까지 반복	
	//2-2-2-2-1. int ny = i + dy; int nx = j + dx;
	//2-2-2-2-2. if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 'W')
	//2-2-2-2-3. cnt++;
	//2-2-2-2. i=0 부터 4까지 반복문종료
	//2-2-2-3. if(cnt > 3)
	//2-2-2-3-1 land.push_back({i,j});
	//2-2-2. 보물섬 지도의 행만큼 반복문 종료
	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			a[i][j] = str[j];			
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int cnt = 0;

			if (a[i][j] = 'L')
			{
				for (int k = 0; k < 4; k++)
				{
					int ny = i + dy[k];
					int nx = j + dx[k];

					if (ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 'W')
						cnt++;
				}
			}
			if (cnt >= 3)
				land.push_back({ i,j });
		}
	}

	//2-2. 보물섬 지도의 열의 길이만큼 반복문 종료
	//2-3. for(int i : land)
	//2-3-1. int min_cnt = 0;
	//2-3-2. void dfs(land[i].first, land[i].second, land[i + 1].first, land[i + 1].second); 
	//2-3-3. fill(visited[0][0],n*m,0);
	//2-3-4. if(max_distance > ret) ret = max_distance
	if (land.size() > 0)
	{
		for (int i = 0; i < land.size() - 1; i++)
		{
			int m_min_distance = n * m;
			dfs(land[i].first, land[i].second, land[i + 1].first, land[i + 1].second);
			fill(&visited[0][0], &visited[n][m], 0);
			for (int i : max_distance)
			{				
				if (min_distance > i)
				{
					min_distance = i;
				}
			}

			if (m_min_distance > ret)
				ret = m_min_distance;
			max_distance.clear();
			min_distance = 0;
		}
	}
	//2-3. for(int i : land) 종료
	cout << ret;
	return 0;
	//2-4. cout << ret;
}

 

예제 출력이 안된다.. ㅠ 한번 더 코드를 반복 숙달해보아야겠다.

 

여러번 코드를 수정해보았으나,, 심신미약 상태로 자꾸 빠져버리므로 해설을 보며 마음의 정화를 시도하자

 

#include<bits/stdc++.h>
using namespace std; 
int n, m, mx, visited[54][54]; 
const int dy[] = {-1, 0, 1, 0}; 
const int dx[] = {0, 1, 0, -1}; 
char a[54][54];
void bfs(int y, int x){
    memset(visited, 0, sizeof(visited)); 
    visited[y][x] = 1; 
    queue<pair<int, int>> q; 
    q.push({y, x}); 
    while(q.size()){
        tie(y, x) = q.front(); q.pop(); 
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i]; 
            int nx = x + dx[i]; 
            if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue; 
            if(visited[ny][nx]) continue; 
            if(a[ny][nx] == 'W')continue;
            visited[ny][nx] = visited[y][x] + 1; 
            q.push({ny, nx});
            mx = max(mx, visited[ny][nx]);
        }
    }
    return;
}
int main(){
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j]; 
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 'L') bfs(i, j); 
        }
    } 
    cout << mx - 1 << "\n";
}

 

정말 간단하게 방문할때마다 visited 를 증감해주어 제일 높은 Max값을 출력해주면 최장거리이다..!!

 

너무 깊게 생각해서 잘 안풀렸나보다.. ㅠ