백준 2589 : 보물섬

문제 링크

---

접근 방법

최장 최단 거리이므로 BFS 결과 중 가장 큰 값을 구한다.

---

삽질했던 부분

트리의 지름

처음 문제에 접근했을 때 효율적으로 풀기 위해서 임의의 한 점에 대해 가장 먼 지점을 구하고,

가장 먼 지점에서부터 BFS를 수행하여 먼 곳까지의 거리를 구하면 답이 나올 수 있다고 생각했다.

즉, 트리의 지름을 구하면 답이 될 것이라고 생각했다.

 

하지만 문제에 주어진 보물섬이 트리가 아닐 수 있기 때문에 오답이 나왔다.

처음에는 트리가 아닐 수 있다는 점이 이해가 되질 않았는데 luniro님의 반례를 통해 이해할 수 있었다.

 

반례

7 7
WLLLLLW
LWLWLWW
LLLWLWW
LWWWLWW
LLLLLWW
LWWWWWW
WWWWWWW

 

우선 문제 그대로 풀이하게 되면 그림 처럼 빨간색이 보물이 묻혀 있는 곳이 되어 거리는 10이 나온다.

 

하지만 트리의 지름을 구하는 방식으로 접근하게 되면 임의의 시작점에서 가장 먼 지점을 구하고

가장 먼 지점에서 BFS로 가장 먼 곳을 구하면 다시 시작점을 구하게 되어 거리는 9가 나오게 된다. 

트리가 아니기 때문에 원하는 대로 값이 나오지 않았다.

 

따라서 모든 점에 대해 일반적인 BFS를 수행하고 최대 거리를 출력한 결과 답이 잘 나올 수 있었다.

---

후기

그리디적인 접근을 할 때 정당성에 대해 검증하는 시간을 더 가져야겠다고 생각했다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 *  2589. 보물섬
 *  최장 최단거리이므로 BFS 결과 중 가장 큰 값을 출력하면 된다.
 */
public class Main {
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static char[][] map;
	static int N, M, ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		for (int i = 0; i < N; i++)
			map[i] = br.readLine().toCharArray();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 'L') 
					bfs(i, j);
			}
		}
		System.out.println(ans);
	}

	static void bfs(int x, int y) {
		boolean visit[][] = new boolean[N][M];
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x, y));
		visit[x][y] = true;
		int dist = -1;
		while (!q.isEmpty()) {
			int sz = q.size();
			for (int k = 0; k < sz; k++) {
				Point p = q.poll();
				for (int d = 0; d < 4; d++) {
					int nx = p.x + dx[d];
					int ny = p.y + dy[d];
					if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny] || map[nx][ny] == 'W')
						continue;
					visit[nx][ny] = true;
					q.add(new Point(nx, ny));
				}
			}
			dist++;
		}
		ans = Math.max(dist, ans);
	}

	static class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}