백준 2589번 보물섬 G5 - BFS

 

아이 눈부셔

 

문제를 잘 읽어도 보물이 없다. 땅과 바다 뿐이다.

눈이 침침한가.

보물은 육지에서 서로 빠르게 가도 가장~~ 먼 위치에 묻혀있다고 한다.

결국 L의 범위를 탐색해서 그 안에서 가장 먼 거리를 찾으면 된다. 

 

최단거리는? BFS 손흥민 봉준호 제이팍 레스고

 

BFS는 탐색안된 영역을 찾아 시작점을 잡아주고 B와 W를 구분한 뒤

BFS 내부에서 

Maxdist= Math.max(Maxdist,dist);

 

를 통해 최대 거리를 찾아주면 된다.

 

import java.io.*;
import java.util.*;
 
public class Main { // Boj_2589_보물섬
    static int N, M, answer, start_x, start_y;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static char[][] arr;
    static boolean[][] visit;
 
    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());
        arr = new char[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(arr[i][j] == 'W') continue;
                answer = Math.max(answer,  bfs(i,j));
            }
        }
        System.out.println(answer);
 
    }
 
    public static int bfs(int x, int y) {
        visit = new boolean[N][M];
 
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x, y, 0});
        visit[x][y] = true;
        int Maxdist = 0;
        while (!que.isEmpty()) {
            int[] now = que.poll();
            int now_x = now[0];
            int now_y = now[1];
            int dist = now[2];
 
            Maxdist= Math.max(Maxdist,dist);
 
            for (int i = 0; i < 4; i++) {
                int next_x = now_x + dx[i];
                int next_y = now_y + dy[i];
                if (range_chk(next_x, next_y) && !visit[next_x][next_y] && arr[next_x][next_y] != 'W') {
                    que.add(new int[]{next_x, next_y, dist + 1});
                    visit[next_x][next_y] = true;
                }
            }
        }
        return Maxdist;
    }
 
    public static boolean range_chk(int x, int y) {
        return 0 <= x && 0 <= y && x < N && y < M;
    }
}

 

큐에 배열을 넣어도~  클래스를 짜서 넣어도~ 뭐든 상관은 없다.