2 분 소요

문제

문제 바로가기

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 ‘.’, ‘#’, ‘O’, ‘R’, ‘B’ 로 이루어져 있다. ‘.‘은 빈 칸을 의미하고, ‘#‘은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, ‘O‘는 구멍의 위치를 의미한다. ‘R‘은 빨간 구슬의 위치, ‘B‘는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 ‘#‘이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

접근방법

문제에서 주의해야할 점은 빨간구슬과 파란구슬을 같이 움직여줘야 한다. 두 구슬 모두 벽이 나올 때까지 이동하고, 서로 만나면 구슬의 원래 위치와 이동해온 방향에 따라서 두 구슬 중에 하나의 위치를 한 칸 이전으로 옮겨주었다. 만약에 이동하면서 구멍을 빠져나오게 된다면 빨간구슬만 나올 경우에만 리턴해주었다.

풀이

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

class Coo {
    int rx, ry, bx, by, cnt;
    Coo(int rx, int ry, int bx, int by, int cnt) {
        this.rx = rx;
        this.ry = ry;
        this.bx = bx;
        this.by = by;
        this.cnt = cnt;
    }
}
public class Main {
    static int N, M;
    static char[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][][][] visit;
    static Coo r, b;
    
    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());
        map = new char[N][M];
        visit = new boolean[N][M][N][M];

        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j] == 'R')
                    r = new Coo(i, j, 0, 0, 0);
                else if(map[i][j] == 'B')
                    b = new Coo(0, 0, i, j, 0);
            }
        }

        System.out.println(bfs());
    }

    public static int bfs() {
        Queue<Coo> q = new LinkedList<>();
        q.add(new Coo(r.rx, r.ry, b.bx, b.by, 1));
        visit[r.rx][r.ry][b.bx][b.by] = true;
        while(!q.isEmpty()) {
            Coo temp = q.poll();
            int rx = temp.rx;
            int ry = temp.ry;
            int bx = temp.bx;
            int by = temp.by;
            int count = temp.cnt;
            if(count > 10) {
                return -1;
            }
            for(int i = 0; i < 4; i++) {
                int rnx = rx;
                int rny = ry;
                int bnx = bx;
                int bny = by;

                boolean gr = false;
                boolean gb = false;

                while(map[rnx + dx[i]][rny + dy[i]] != '#') {
                    rnx += dx[i];
                    rny += dy[i];
                    if(map[rnx][rny] == 'O') {
                        gr = true;
                        break;
                    }
                }

                while(map[bnx + dx[i]][bny + dy[i]] != '#') {
                    bnx += dx[i];
                    bny += dy[i];
                    if(map[bnx][bny] == 'O') {
                        gb = true;
                        break;
                    }
                }

                if(gb) continue;
                if(gr) return count;

                if(rnx == bnx && rny == bny) {
                    if(i == 0) {
                        if(rx < bx) bnx++;
                        else rnx++;
                    }
                    else if(i == 1) {
                        if(rx < bx) rnx--;
                        else bnx--;
                    }
                    else if(i == 2) {
                        if(ry < by) bny++;
                        else rny++;
                    }
                    else {
                        if(ry < by) rny--;
                        else bny--;
                    }
                }

                if(!visit[rnx][rny][bnx][bny]) {
                    q.add(new Coo(rnx, rny, bnx, bny, count + 1));
                    visit[rnx][rny][bnx][bny] = true;
                }
            }
        }
        return -1;
    }
}

댓글남기기

참고