BOJ_2589 : 보물섬

👉 문제링크

2589번: 보물섬

---

---

🔸 문제 분석 🔸

• 육지는 상하좌우로 건널 수 있는 땅이다.
• 두 보물은 한 육지에 있으며, 최단 거리가 가장 긴 두 위치에 있다.
• bfs로 가장 멀리 퍼진곳을 찾으면, 최단 거리 중 가장 긴 거리이다.
• 두 보물 사이를 이동하는 시간을 출력한다.

🔸 코드 🔸

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

public class Main {
	static int max = 0;
	static int[] di = { -1, 0, 1, 0 };
	static int[] dj = { 0, 1, 0, -1 };
	static int r, c;
	static char[][] map;

	public static class Index {
		int i, j;

		public Index(int i, int j) {
			this.i = i;
			this.j = j;
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new char[r][c];

		for (int i = 0; i < r; i++) {
			map[i] = br.readLine().toCharArray();
		}

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] == 'L') {
					max = Math.max(max, bfs(i, j));
				}

			}
		}
		System.out.println(max);

	}

	private static int bfs(int i, int j) {
        boolean[][] visited = new boolean[r][c];
		Queue<Index> queue = new LinkedList<>();
		queue.add(new Index(i, j));
		visited[i][j] = true;
		int cnt = -1;

		while (!queue.isEmpty()) {
			int num = queue.size();
			cnt++;
			for (int t = 0; t < num; t++) {
				Index now = queue.poll();

				for (int d = 0; d < 4; d++) {
					int nexti = now.i + di[d];
					int nextj = now.j + dj[d];
					if (nexti >= 0 && nexti < r && nextj >= 0 && nextj < c && map[nexti][nextj] == 'L'
							&& !visited[nexti][nextj]) {
						queue.add(new Index(nexti, nextj));
						visited[nexti][nextj] = true;
				}}
			}
		}
		return cnt;

	}

}

🔸 코드 해석 🔸

• 각 육지별로 BFS로 최단 거리의 최대값을 구한다.
• 그 중 최대값을 출력한다.

---

🔸 end 🔸

• 최단거리라는 점에서 bfs가 가장 먼저 떠올랐고, 그 중 최대값이라해서 업데이트만 하면 될 것같았다.
• 가로 세로가 50 이하이므로 bfs, dfs 모두 가능하다고 생각했다.