[백준 2589] 보물섬 (자바)

 

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

 

1644번: 소수의 연속합

 

 

난이도 : 골드 5

 

BFS를 이용한 브루트 포스입니다.

땅의 한 지점에서 BFS로 퍼져나가며 가장 큰 수가 가장 먼 거리입니다.

모든 지점에서 BFS를 통해 먼 거리를 최신화시켜줍니다.

---

전역 변수 

n, m = 지도의 가로, 세로의 크기

answer = 가장 먼 거리(답)

st = 땅의 좌표를 저장하는 스택

dx, dy = 좌표 이동시 사용할 배열

메소드

void main 

입력 값을 받고 L(땅) 일 때 스택에 push 합니다.

모든 좌표값에 대해 먼 거리를 탐색하여 답을 찾고 출력합니다.

(find 호출)

 

void find

파라미터로 받은 시작 좌표값부터 BFS로 길이를 잽니다. 

(check 호출)

 

boolean check

이동할 좌표값이 정상 값인지 검사하고 땅(L)인지 검사합니다.

 

class Point

x, y 좌표값과 거리(dis)를 가집니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class p2589 {
    
    static int n, m, answer;
    static char map[][];
    static Stack<Point> st;
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());
        answer = 0;
        map = new char[n][m];
        st = new Stack<>();
        for(int i = 0; i < n; i++) {
            String line = br.readLine();
            for(int j = 0; j < m; j++){
                map[i][j] = line.charAt(j);
                if(map[i][j] == 'L')
                    st.push(new Point(i, j, 0));
            }
        }
        while(!st.isEmpty()) {
            Point now = st.pop();
            find(now);
        }
        System.out.println(answer);
    }
    
    public static void find(Point now) {
        boolean visit[][] = new boolean[n][m];
        Queue<Point> q = new LinkedList<>();
        visit[now.x][now.y] = true;
        q.offer(now);
        
        while(!q.isEmpty()) {
            Point p = q.poll();
            answer = Math.max(p.dis, answer);
            
            for(int i = 0; i < 4; i++) {
                int x = p.x + dx[i];
                int y = p.y + dy[i];
                
                if(check(x, y) && !visit[x][y]) {
                    visit[x][y] = true;
                    q.offer(new Point(x, y, p.dis + 1));
                }
            }
        }
    }
    
    public static boolean check(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m && map[x][y] == 'L';
    }
    
    static class Point{
        int x, y, dis;
        
        Point(int x, int y, int dis){
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }
}