BOJ - 열쇠(9328)

문제(링크)

조건이 많이 까다로운 BFS 문제였습니다.

먼저, 빌딩 밖으로 나갈 수 있기 때문에 입력받는 배열 외에 겉에 한 줄을 더 감싸주었습니다.( 이렇게 하면 (0,0)에서 시작하여 항상 어디든지 갈 수 있습니다.)

열쇠와 문에 관련된 조건이 까다로웠는데, 다음과 같이 해결했습니다.

- 열쇠를 만날 시
해당 열쇠를 배열에 추가하고(havekey[]), 리스트에 저장된 문들 중 열쇠에 해당하는 문들을 큐에 다시 넣습니다.( 그 문부터 다시 탐색합니다. )

- 문을 만날 시
1. havekey[] 배열에 등록된 열쇠라면(열린 문이라면) 통과합니다.
2. 잠긴 문이라면 문 리스트에 해당 좌표를 추가합니다.(다시 올 수 있게)

나머지는 일반적인 BFS와 같습니다.

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

public class Main {

    public static int T, N, M;
    public static char[][] map;
    public static boolean[][] visit;
    public static int[] mv1 = {0,0,1,-1};
    public static int[] mv2 = {1,-1,0,0};
    public static boolean[] havekey;
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            map = new char[N + 2][M + 2];
            visit = new boolean[N + 2][M + 2];
            havekey = new boolean[26];

            for (int j = 0; j <= N + 1 ; j++) {
                if(j == 0 || j == N + 1){
                    for (int k = 0; k <= M + 1 ; k++) {
                        map[j][k] = '.';
                    }
                }
                else {
                    String s = br.readLine();
                    for (int k = 0; k <= M + 1; k++) {
                        if (k == 0 || k == M + 1)
                            map[j][k] = '.';
                        else {
                            map[j][k] = s.charAt(k - 1);
                        }
                    }
                }
            }
            String key = br.readLine();
            if(key.charAt(0) != '0'){
                for (int j = 0; j < key.length() ; j++) {
                    char now = key.charAt(j);
                    havekey[now - 'a'] = true;
                }
            }
            bw.write(BFS() + "\n");
        }
        bw.flush();
        bw.close();
    }
    public static int BFS(){
        Queue<XY> q = new LinkedList<>();
        ArrayList<XY> doors = new ArrayList<>();
        q.offer(new XY(0, 0, -1));

        int cnt = 0;

        while(!q.isEmpty()){
            XY now = q.poll();

            for (int i = 0; i < 4 ; i++) {
                int next_x = now.x + mv1[i];
                int next_y = now.y + mv2[i];

                if(next_x < 0 || next_y < 0 || next_x >= N + 2 || next_y >= M + 2)  continue;
                char nextxy = map[next_x][next_y];
                if(nextxy == '*')  continue;
                if(visit[next_x][next_y])   continue;
                visit[next_x][next_y] = true;

                if(nextxy >= 'A' && nextxy <= 'Z'){
                    if(havekey[nextxy - 'A'])
                        q.offer(new XY(next_x, next_y, -1));
                    else
                        doors.add(new XY(next_x, next_y, nextxy - 'A'));
                }
                else if(nextxy >= 'a' && nextxy <= 'z'){
                    havekey[nextxy - 'a'] = true;
                    for (int j = 0; j < doors.size() ; j++) {
                        XY now_door = doors.get(j);

                        if(now_door.door == nextxy - 'a'){
                            q.offer(new XY(now_door.x, now_door.y, -1));
                            now_door.door = -1;
                        }
                    }
                    q.offer(new XY(next_x, next_y, -1));
                    map[next_x][next_y] = '.';
                }
                else if(nextxy == '$'){
                    map[next_x][next_y] = '.';
                    q.offer(new XY(next_x, next_y, -1));
                    cnt++;
                }
                else{
                    q.offer(new XY(next_x, next_y, -1));
                }
            }
        }
        return cnt;
    }
}

class XY{
    int x;
    int y;
    int door;
    public XY(int x, int y, int door){
        this.x = x;
        this.y = y;
        this.door = door;
    }
}