[백준] 2589번 - 보물섬 / C++

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아 나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는 데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

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

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

 

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50 이하이다.

 

출력

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

 

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct pos
{
	int r;
	int c;

	void init(int r, int c)
	{
		this->r = r;
		this->c = c;
	}
};

int N;
int M;
bool map[51][51];

bool in_range(pos p)
{
	if (p.r < 0 || p.r >= N || p.c < 0 || p.c >= M)
		return false;
	return true;
}

int treasure_hunt(int r, int c)
{
	queue<pos> q;
	pos curr, next;
	bool visit[51][51];
	int d[] = {-1, 1, 0, 0};
	int i, s, size, cnt = 0;

	memset(visit, false, sizeof(visit));
	curr.init(r, c);
	visit[r][c] = true;
	q.push(curr);
	while (!q.empty())
	{
		size = q.size();
		for (s = 0; s < size; s++)
		{
			curr = q.front();
			q.pop();
			for (i = 0; i < 4; i++)
			{
				next.init(curr.r + d[i], curr.c + d[3 - i]);
				if (!in_range(next))
					continue;
				if (map[next.r][next.c] || visit[next.r][next.c])
					continue;
				visit[next.r][next.c] = true;
				q.push(next);
			}
		}
		cnt++;
	}
	return cnt - 1;
}

int main()
{
	int i, j, answer = 0;
	char c;

	cin >> N >> M;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			cin >> c;
			if (c == 'W')
				map[i][j] = 1;
		}
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (!map[i][j])
				answer = max(answer, treasure_hunt(i, j));
		}
	}
	cout << answer << endl;
	return 0;
}

 

육지인 칸의 거리의 최댓값을 구하면 된다. 모든 육지인 칸을 시작점으로 하여 각 칸에서 가장 멀리 있는 육지인 칸 사이의 거리를 구한다. 이때 bfs를 사용하여 가까운 거리의 육지인 칸부터 확인하고 더 이상 갈 수 있는 육지인 칸이 없을 때까지 탐색한다. 탐색을 마친 후 cnt의 값은 그다음으로 갈 수 있는 육지인 칸까지의 거리인데 그러한 칸이 없으므로 -1을 해주어 현재까지 방문한 칸 중 최대 거리를 리턴한다. 이러한 방식으로 최댓값을 구하면 보물 간 최단 거리를 알 수 있다.

 

링크

2589번: 보물섬

inbdni/Baekjoon