[BOJ] 2589번 보물섬 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

	static class Pos {
		int r;
		int c;
		int cost;

		public Pos(int r, int c, int cost) {
			super();
			this.r = r;
			this.c = c;
			this.cost = cost;
		}
	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static int N, M, max;
	static char[][] map;
	static boolean[][] used;

	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());
		max = Integer.MIN_VALUE;
		map = new char[N][M];

		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 'L') {
					used = new boolean[N][M];
					used[i][j] = true;
					bfs(new Pos(i, j, 0));
				}
			}
		}
		System.out.println(max);
	}

	private static void bfs(Pos start) {
		Queue<Pos> q = new LinkedList<>();
		q.add(start);
		while (!q.isEmpty()) {
			Pos now = q.poll();
			int r = now.r;
			int c = now.c;
			int cost = now.cost;
			max = Math.max(max, cost);

			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
				if (used[nr][nc] || map[nr][nc] == 'W') continue;
				used[nr][nc] = true;
				q.add(new Pos(nr, nc, cost+1));
			}
		}
	}
}

📄 해설

• 모든 육지에서 BFS 를 수행한다 라는 접근을 하면 쉽게 해결이 가능함
• 리를 나타내기 위해 Pos 클래스의 멤버변수로 cost 를 추가
• 지도를 탐색하며 육지를 나타내는 L 을 찾을 때마다 BFS 를 수행하며, 수행 시 마다 방문 배열을 초기화하고 수행
• BFS 수행 시 큐에서 노드를 꺼낼 때 마다 최댓값 갱신을 해줌