백준 2589번 : 보물섬 java

이 문제는 bfs를 이용하여 섬 안에서 가장 먼 거리에 보물을 묻을 때 보물 간의 거리를 구하는 문제입니다.

이 문제를 풀 때는 브루트포스 알고리즘을 사용해야 합니다.

지도의 각 칸을 탐색하면서 탐색한 칸이 땅일 때 연결된 땅들을 전부 탐색하면서 가장 거리가 먼 땅을 찾습니다.

코드를 보면서 조금 더 설명드리도록 하겠습니다.

---

import java.io.*;
import java.util.*;

public class Main {
    static int row, col;
    static char[][] map;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};
    static int max = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());

        map = new char[row][col];
        boolean[][] visited = new boolean[row][col];

        for(int i = 0; i<row; i++){
            String input = br.readLine();

            for(int j = 0; j<col; j++) {
                map[i][j] = input.charAt(j);

                if(map[i][j] == 'W')
                    visited[i][j] = true;
            }
        }

        treasureFind(visited);

        System.out.println(max);
    }

    static void treasureFind(boolean[][] visited){
        for(int i = 0; i<row; i++){
            for(int j = 0; j<col; j++){
                if(visited[i][j])
                    continue;

                //원본을 바꾸지 않게 새로운 visited를 만들어서 보내줌
                boolean[][] visitedCopy = new boolean[row][];
                for(int k = 0; k<row; k++)
                    visitedCopy[k] = visited[k].clone();

                treasureFind(i, j, visitedCopy);
            }
        }
    }

    static void treasureFind(int startRow, int startCol, boolean[][] visited){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(startRow, startCol, 0));
        visited[startRow][startCol] = true;

        while(!q.isEmpty()){
            Node a = q.poll();
            max = Math.max(max, a.cnt);

            for(int i = 0; i<4; i++){
                int dr = a.row + dR[i];
                int dc = a.col + dC[i];

                if(dr<0||dc<0||dr>=row||dc>=col)
                    continue;
                if(visited[dr][dc])
                    continue;

                q.offer(new Node(dr, dc, a.cnt+1));
                visited[dr][dc] = true;
            }
        }
    }
}
class Node{
    int row, col, cnt;

    Node(int row, int col, int cnt){
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
}

각 칸을 순회하면서 연결된 땅들을 bfs를 이용하여 탐색했습니다.

이 문제를 풀 때 유의하셔야하는 점은 아래의 코드입니다.

//원본을 바꾸지 않게 새로운 visited를 만들어서 보내줌
boolean[][] visitedCopy = new boolean[row][];
for(int k = 0; k<row; k++)
    visitedCopy[k] = visited[k].clone();

visited 배열을 매개변수로 보낼 때 visited 배열의 레퍼런스가 넘어갑니다.

따라서 treasureFind 함수에서 visited 배열을 수정하면 원본 visited 배열도 수정되므로 visited 배열의 클론인 visitedCopy 배열을 만들어 보냄으로써 원본 visited가 훼손되는 것을 방지하였습니다.