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

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

2589번: 보물섬

문제

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

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

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

입력

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

출력

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

 

전형적인 BFS문제입니다.

가로 세로의 크기는 모두 50이하 이므로 모든 육지 구역의 보물섬 위치를 확인해도 시간이 초과되지 않습니다.

완전탐색 + BFS로 해결하였습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;


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

int adj[51][51];
int visited[51][51];

const int dy[] = { 1, -1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };

int Length;
queue<pl> q; 

bool isValid(int y, int x, int col,int row) {
	return (1 <= y && y <= col && 1 <= x && x <= row);
}

void BFS(int col, int row) {
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

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

			if (!isValid(ny, nx, col, row) || visited[ny][nx] != 0) continue;
			if (adj[ny][nx] == 0) {
				q.push({ ny, nx });
				visited[ny][nx] = visited[y][x] + 1;
				Length = max(Length, visited[ny][nx]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int col, row;
	cin >> col >> row;
	for (int y = 1; y <= col; y++) {
		string s; cin >> s;
		for (int x = 0; x < s.size(); x++) {
			if (s[x] == 'W') adj[y][x + 1] = 1;
			else adj[y][x + 1] = 0;
		}
	}

	int Answer = 0;
	for (int i = 1; i <= col; i++) {
		for (int j = 1; j <= row; j++) {
			if (!adj[i][j]) {
				memset(visited, 0, sizeof(visited));
				q.push({ i, j });
				visited[i][j] = 1;
				Length = 0;
				BFS(col, row);
				Answer = max(Answer, Length);
			}
		}
	}
	cout << Answer-1 << endl;

	return 0;
}