본문 바로가기

OJ

[BOJ] 28130 슈넬치킨 랑데부 (JAVA)

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

 

28130번: 슈넬치킨 랑데부

첫째 줄에 $N$과 $M$이 주어진다. $(3\leq N,M\leq 1\,000)$ 둘째 줄부터 $N$줄에 걸쳐 연병장에 대한 정보가 연병장 가장 위쪽 행의 정보부터 차례대로 각각 길이 $M$의 문자열로 주어진다. 여기서 A는 상

www.acmicpc.net

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

public class Main {
	
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int dir = 3;
        Queue<int[]> q = new LinkedList<>();
        int[] pos = new int[2];
        char[][] map = new char[N][M];
        int[][] visited = new int[N][M];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'B') {
                    pos[0] = i;
                    pos[1] = j;
                    map[i][j] = '.';
                    if (i == 0 && j < M - 1) dir = 0;
                    else if (j == M - 1 && i < N - 1) dir = 1;
                    else if (i == N - 1 && 0 < j) dir = 2;
                } else if (map[i][j] == 'A') q.offer(new int[] { i, j });
            }
        }

        int[] dr = {  0,  1,  0, -1 };
        int[] dc = {  1,  0, -1,  0 };
        int time = 1;

        while (!q.isEmpty()) {
            int size = q.size();

            while (0 < size--) {
                int[] now = q.poll();

                for (int next = 0; next < 4; next++) {
                    int nr = now[0] + dr[next];
                    int nc = now[1] + dc[next];

                    if (0 <= nr && nr < N && 0 <= nc && nc < M && visited[nr][nc] == 0 && map[nr][nc] == '.') {
                        q.offer(new int[] { nr, nc });
                        visited[nr][nc] = time;
                    }
                }
            }

            pos[0] += dr[dir];
            pos[1] += dc[dir];

            if (visited[pos[0]][pos[1]] != 0) {
                if ((visited[pos[0]][pos[1]] + time) % 2 == 0) {
                    System.out.print(time);
                    return;
                } else break;
            }

            if ((pos[0] == 0 || pos[0] == N - 1) && (pos[1] == 0 || pos[1] == M - 1)) dir = (dir + 1) % 4;
            time++;
        }

        System.out.print(-1);

    }

}