[BOJ - JAVA] 2589 - 보물섬 (BFS)

# 주소

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

2589번: 보물섬

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
public class Main{
    static int n, m;
    static int[][] arr;
    static int[] dx = {1,0,0,-1};
    static int[] dy = {0,-1,1,0};
    static boolean[][] visit;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        for(int i = 0; i < n; i++){
            String str = scan.next();
            for(int j = 0; j < m; j++){
                if(str.charAt(j) == 'L')
                    arr[i][j] = 1;
                else
                    arr[i][j] = 0;
            }
        }
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] == 1) {
                    visit = new boolean[n][m];
                    int val = value(i, j, 0);
                    result = Math.max(result, val);
                }
            }
        }
        System.out.println(result);
    }
    public static int value(int x, int y, int cnt){
        visit[x][y] = true;
        int val = 0;
        LinkedList<Point> queue = new LinkedList<>();
        queue.offer(new Point(x,y,0));
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                    continue;
                }
                if(arr[nx][ny] == 1 && visit[nx][ny] == false){
                    visit[nx][ny] = true;
                    queue.offer(new Point(nx,ny,now.cnt+1));
                    val = Math.max(val, now.cnt);
                }
            }
        }
        return val + 1;
    }
    public static class Point{
        int x;
        int y;
        int cnt;
        public Point(int x, int y, int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

오랜만입니다.

연말이라서 학원 보강도 하고 이리저리 움직일 곳도 많아서 포스팅이 늦었습니다.

때문에 쌓인 공부량도 넘 많아져서 열심히 달려야겠어요 ㅠㅠ...

이번엔 BFS문제를 가져와봤습니다.

저는 입력받은 L 또는 R을 숫자로 치환해서 int 타입의 2차원 arr를 생성했습니다.

그래서 육지부분은 1, 바다 부분은 0으로 표기한 arr를 만들었습니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if(arr[i][j] == 1) {
            visit = new boolean[n][m];
            int val = value(i, j, 0);
            result = Math.max(result, val);
        }
    }
}

이중 for문으로 arr가 1인 부분에 대해서 value함수를 실행합니다. (원래 함수 2개 만들려고 했는데 자세히 읽어보니까 1개만 해도 되네요. 그래서 저 value가 원래의 bfs입니다.)

그리고 vlaue(i,j,0);을 int val에 담고 기존의 result와 val을 비교하여 가장 큰 val값을 result에 담을 것입니다.

value함수를 (bfs) 살펴봅시다.

queue를 선언하는데, 제네릭 타입엔 Point가 들어갑니다.

근데 우리는 Point를 원래 x랑 y를 담기 위해선 awt.Point라는 것을 import해주었지만 이렇게 인자가 3개가 들어갈 경우에는 새로 class를 만들어서 사용해주어야 합니다.

따라서 제일 밑에 저는

public static class Point{
    int x;
    int y;
    int cnt;
    public Point(int x, int y, int cnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

이렇게 만들었습니다.

자 이후 now 점은 queue.poll()한 것의 현재점입니다.

이 now점에 dx와 dy의 이동에 따라 nx, ny가 결정됩니다.

그런데 이 nx, ny가 0이하거나 n 또는 m이상이 될 경우는 더 이상 진행할 수 없으므로 continue합니다.

그리고 그렇지 않을경우 arr가 1이고 visit은 false일 때 visit은 true로 바꾸어 주고 queue에는 nx, ny, 현재 점의 cnt에 + 1 하여 원래 value에 넣고 돌렸던 x, y점에서 멀어질 때마다 한 칸씩 이동하여 cnt + 1해줍니다.

그리고 이 val에는 val와 now.cnt를 비교하여 더 큰값을 저장하는데요.

마지막에 가장 멀리 있는 nx, ny점에 대하여 위의 예제를 예로 했을 때

(3,0) 부터 (4,1)까지의 이동 거리인 8이 정답이 나와야 합니다.

그런데, (4,2)로 도착한 순간 더 이상 if문으로 가용할 수가 없어서 val에는 이전에 담긴 값인 7이 저장된 채로 내려옵니다.

따라서 최정 목적지인 (4,1)까지 이동하기 위해 val + 1해주어 return해주면 최종적인 정답이 됩니다.

감사합니다.