2589번: 보물섬

문제 설명

https://www.acmicpc.net/problem/2589

2589번: 보물섬

[문제]

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

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

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

 

[입력]

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

 

[출력]

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

 

[예제 입력 1]

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

[예제 출력 1]

8

---

풀이

 결국 문제의 핵심 각 육지에서 가장 긴 최단 경로를 반환하면 되는 것이기 때문에, 굳이 해당 지점이 어디인지를 기억할 필요도 없이 거리만 계산하면 된다. 그러기 때문에 단순하게 배열을 전체를 돌아가며 'L'이라 표시된 육지에서 BFS 함수를 돌려 해당 지점의 가장 긴 최단 경로를 얻어내고, 이를 모든 육지 지점에서 비교하여 답을 얻어내면 된다.

 추가적으로 시간을 더 줄여보고자, 단순히 육지중에서 상하좌우가 모두 육지인 곳은 탐색 함수를 부를 필요 없이 건너뛰게 하여, 시간을 줄일 수 있었다.

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

using namespace std;

vector<string> map;
int visited[50][50];

struct infor {//위치 정보
	int r, c, cost;
};

bool check(int R, int C, int r, int c) {//탐색할 만한 곳인지
	if (0 == r || r == R - 1 || 0 == c || c == C - 1) //지도의 가장자리는 탐색 ok
		return true;
	//상하좌우 모두 육지면 탐색 X
	if (map[r + 1][c] == 'L' && map[r - 1][c] == 'L' && map[r][c + 1] == 'L' && map[r][c - 1] == 'L')
		return false;

	return true;
}

int findTheLongestWay(int R, int C, int r, int c) {//가장 긴 최단경로 탐색
	int maxPathCost = 0;
	queue<infor> q;
	memset(visited, 0, sizeof(visited));

	q.push({ r, c, 0 });

	while (!q.empty()) {
		infor here = q.front(); q.pop();

		if (0 > here.r || here.r >= R || 0 > here.c || here.c >= C)//인덱스 밖
			continue;

		if (map[here.r][here.c] == 'W' || visited[here.r][here.c] == 1)//바다거나 방문한적이 있으면
			continue;

		visited[here.r][here.c] = 1;
		maxPathCost = max(maxPathCost, here.cost);//최다 경로 저장

		++here.cost;

		--here.r;//상
		q.push(here);
		++here.r; ++here.c;//우
		q.push(here);
		here.c -= 2;//좌
		q.push(here);
		++here.c; ++here.r;//하
		q.push(here);
	}

	return maxPathCost;
}

int main() {
	int R, C;
	int answer = 0;
	cin >> R >> C;

	for (int i = 0; i < R; i++) {//지도 초기화
		string s;
		cin >> s;
		map.push_back(s);
	}

	for (int i = 0; i < R; i++) {//탐색
		for (int j = 0; j < C; j++) {
			if (map[i][j] == 'L'&&check(R,C,i,j)) {
				answer = max(answer, findTheLongestWay(R, C, i, j));
			}
		}
	}

	cout << answer;

	return 0;
}

---

결과

위에는 탐색 함수 호출 조건을 설정한 경우, 아래는 단순히 모든 육지 지점에서 탐색 함수를 호출한 경우이다.