백준 2589번 - 보물섬

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

2589번: 보물섬

 

풀이 과정

 연결 컴포넌트 중 가장 큰 최단거리를 구하는 문제이다. BFS()로 노드를 탐색하며 최단 거리를 구하고 MAX값을 갱신해주면 된다. 단, 최단거리는 같은 연결 컴포넌트더라도, 거리 측정을 시작하는 노드 위치에 따라 바뀐다. 따라서,  매번 visited를 초기화 해주고 'L' 마다 BFS()를 실행하며 최단 거리를 구하고 MAX를 갱신했다.

 

느낀 점

 'L'일 경우에만 BFS()가 실행 되도록 했어야 했는데, 일단 BFS를 실행하고 첫 노드를 큐에 넣은 후부터 검사를 했다. 이때문에 오답을 한 번 받게 되었다. 항상 엄밀한 조건 설정이 필요하다.

 

#include<bits/stdc++.h>
using namespace std;

const int NMX = 51;
int n, m, ret;
int visited[NMX][NMX], my[4] = {1, 0, -1, 0}, mx[4] = {0, 1, 0, -1};
char temp;
bool mp[NMX][NMX];
//BFS() 구현 : 최단 거리 반환
int bfs(int y, int x) {
	if (!mp[y][x]) return 0;
	int mx_cnt = 0;
	queue < pair<int, int>> q;
	q.push({ y, x });
	visited[y][x] = 1;

	do {
		for (int i = 0; i < 4; i++) {
			int ny = my[i] + q.front().first;
			int nx = mx[i] + q.front().second;
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] != 0 || !mp[ny][nx]) continue;
			visited[ny][nx] = visited[q.front().first][q.front().second] + 1;
			mx_cnt = max(mx_cnt, visited[ny][nx]);
			q.push({ ny, nx });
		}
		q.pop();
	} while (q.size());

	return mx_cnt;
}
//'L'과 'W'에 따라 지도 입력
void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp == 'W') mp[i][j] = 0;
			else mp[i][j] = 1;
		}
	}
	return;
}
//BFS()를 실행하며 보물 간 최대 거리 구하기
void find_ret() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			fill(&visited[0][0], &visited[0][0] + NMX * NMX, 0);
			ret = max(bfs(i, j), ret);
		}
	}
}
//결과 출력
void output() {
	cout << ret - 1 << "\n";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();

	find_ret();

	output();

	return 0;
}