[백준] 2589번 보물섬(java)

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

2589번: 보물섬

이 문제를 해석해 보면, 육지에서 갈 수 있는 끝지점과 끝지점사이의 거리를 구하는 것이다.

단 이동할 때, 가장 빠른 방법으로 간다 즉 BFS를 사용하라는 것이다.

바로 풀어보자.

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main{
    static int[][] result;
    static char[][] map;
    static int[] dy ={1,0,-1,0};
    static int[] dx ={0,-1,0,1};
    static int N;
    static int M;
    static int max;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); //세로
        M = sc.nextInt(); //가로
        map = new char[N][M];
        for (int i = 0; i < N; i++){
            String line = sc.next();
            for (int j = 0; j < M; j++){
                map[i][j] = line.charAt(j);
            }
        }

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

    static void getResult(int y, int x){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y,x});
        result[y][x] = 1;

        while (!queue.isEmpty()) {
            int[] move = queue.poll();

            for (int i = 0; i < 4; i++) {
                int moveY = move[0] + dy[i];
                int moveX = move[1] + dx[i];

                if (0<=moveY && moveY <N && 0<=moveX && moveX <M){
                    if (map[moveY][moveX]=='L' && result[moveY][moveX]==0){
                        queue.add(new int[]{moveY, moveX});
                        result[moveY][moveX] = result[move[0]][move[1]]+1;
                        max = Math.max(max, result[moveY][moveX]-1);
                    }
                }
            }
        }
    }
}

해설

네 방향으로 이동가능한 경우 dy, dx를 설정해 주는 것이 문제 풀이에 있어 매우  편하다.

우선 map에 육지와 바다를 표시해 준다.

이제 각 육지마다 BFS를 해준다.

근데 중요한 것이 시작점이 계속 달라지기 때문에 값을 넣을 result를 초기화를 계속 진행해 주었다.

방문여부는 배열 초기값인 0이면 아직 방문을 안 한 것으로 생각하기로 하였다.

그래서 첫 시작 포인트가 1이 된다.

또한 이로 인해 마지막 max를 구하는 부분에서 -1을 하게 된다.

알고리즘 BFS 설명을 한 글에 이와 비슷한 문제 및 풀이가 있기에 이 정도로 설명해도 충분할 것이라 생각된다.

 

 

배운 점

매우 흔한 BFS문제이기에 푸는데 어렵지는 않았다.

다만 처음에 중복체크를 0으로 하고 첫 시작점을 0으로 두었기에 다시 첫 시작점을 탐색해서,

틀렸었다. 이러한 사소한 실수도 줄이도록 꼼꼼하게 풀어야겠다.