백준저지 2589번 보물섬 (Java)

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

2589번: 보물섬

 

 

접근 방법

변수

max : 답이 될 최댓값

cntL : 입력받을 때 센 L의 개수. L이 1이라면 답은 무조건 1이다.

 

메서드

int getCount(int x, int y, char[][] map) : 현재 위치 x,y와 입력 받은 map[][]으로 BFS를 수행하여 답이 될 이동횟수를 리턴시킨다.

 

코드

0. 입력을 받는다. 입력 받을 때 L 개수를 세서 cntL에 저장한다.

1. 지도 위 모든 칸을 돌면서 L일 때마다 BFS 탐색을 시작한다.

2. BFS 탐색 방법은 다음과 같다.

  2-1. 방문체크를 위한 boolean 2차원 배열을 만든다.

  2-2. 현재 위치를 큐에 넣고, 큐가 완전히 빌 때까지 다음과 같은 작업을 반복한다.

    2-2-a. 한 칸을 이동했는지 확인하기 위한 boolean 변수인 lastVisited를 false로 초기화한다.

    2-2-b. 큐에서 1개를 우선 빼고, 4방 탐색을 한다.

    2-2-c. 지도 안에 있고, 방문 안 했고, L이라면 방문했다고 표시하고, 큐 안에 해당 위치를 넣는다. 그리고 이동을 했기 때문에 lastVisited를 true로 바꾼다.

    2-2-d. lastVisited가 true라면 cnt 값을 1 증가시킨다.

3. 구한 cnt 값을 리턴시킨다.

4. max값을 더 큰 값으로 바꾼다.

5. map을 모두 확인한 뒤에 cntL 값이 1이라면 답은 1로 한다. 그 외는 max 값이 답이 된다.

 

 

생각

lastVisited가 필요했던 이유

입력이 다음과 같이 주어진다면, 답은 2다.  파란색으로 표시된 1 -> 2 -> 3 순서대로, 빨간선 따라 이동하는 것이 답이다.

그런데 while문 안에서 돌면서 cnt 값이 증가될 때 불필요하게 1이 증가된다.

파란색 번호 및 위치	큐 크기	큐에 새로 담는 위치 개수	실제로 이동 여부	cnt 값
1 (0,1)	1	1	1 (2로 갈 것)	1
2 (0,0)	1	1	1 (3으로 갈 것)	2
3 (1,0)	1	0	0 (더 이상 이동하지 않음)	2

그래서 큐에 새로 담는 여부가 실제 이동 여부라고 판단하여 lastVisited가 true일 때만 cnt 값을 증가시켰다.

 

그런데 이렇게 하면 L의 개수가 1일 때 답이 0으로 나온다. L이 자기 혼자이기 때문에 이동을 안하기 때문이다. 그래서 마지막에 L의 개수가 1일 때는 1이 답으로 출력되도록 만들었다.

 

풀긴 했지만 조금 더 간단하게 정리해서 풀 수 있으면 좋겠다.

 

 

코드

// 백준저지 2589번 보물섬 https://www.acmicpc.net/problem/2589

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 BOJ2589 {

    static int N, M;
    static int[][] d = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    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());
        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = (br.readLine()).toCharArray();

        }

        int max = 0; // 최댓값 -> 답
        int cntL = 0; // L의 개수
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'L') {
                    max = Math.max(max, getCount(i, j, map));
                    cntL++;
                }
            }
        }

        max = (cntL == 1) ? 1 : max; // L이 1개라면 답은 1, 그외는 max가 답
        System.out.println(max);
    }

    private static int getCount(int x, int y, char[][] map) {
        int cnt = 0;
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { x, y });
        visited[x][y] = true;
        boolean lastVisited = false; // 맵 안에서 새롭게 이동을 했는지 확인하기 위함

        while (!q.isEmpty()) {
            int qSize = q.size();
            lastVisited = false;

            for (int j = 0; j < qSize; j++) { // 큐 사이즈만큼 반복
                int[] cur = q.poll();
                x = cur[0];
                y = cur[1];

                for (int i = 0; i < 4; i++) {
                    int dx = x + d[i][0];
                    int dy = y + d[i][1];
                    if (dx >= 0 && dx < N && dy >= 0 && dy < M && !visited[dx][dy] && map[dx][dy] == 'L') {
                        visited[dx][dy] = true;
                        q.offer(new int[] { dx, dy });
                        lastVisited = true; // 새롭게 방문을 했다고 표시 -> 이동을 했으므로
                    }
                }
            }

            if (lastVisited) { // 방문을 새로 한 경우만 cnt 증가
                cnt++;
            }
        }

        return cnt;
    }
}