[백준] 9328번 : 열쇠

9328번: 열쇠

---

[BFS + 비트마스킹]

정말 맞왜틀? 이 질문이 여러번 나왔던 문제. 뜻밖의 반례를 찾아서 다행히 AC를 받았다.

1
6 6
.*****
.A$B$*
******
.C$D$*
******
**ac**
0

answer : 2

기존 코드는 위의 반례에서 무한루프를 돌았다. 그 이유는 망각해버렸으나 어떤 열쇠를 갖고있는지에 대한 정보 (key)를 전역변수로 두어 BFS내에서 공유하게 했더니 TLE를 피했다.

 

그리고 "상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공간이나 문을 통해 빌딩 안팎을 드나들 수 있다. "라고 하므로, (0, 0)에서 BFS를 시작한다. 즉 건물 밖에서 안으로 들어가 BFS 탐색을 수행한다.

 

비트마스킹이란 예를 들어 열쇠 a, c, d, e가 있다고 하자. 이때 어떤 열쇠를 갖는지에 대해 비트마스킹으로 표현했을 때

 

0b00 0000 0000 0000 0000 0001 1101

 

이다. 알파벳은 'a'~'z'까지 총 26개이므로 26비트를 가져야하고, 이는 약 620만 정도를 나타내어 int로 충분히 표현 가능하다.

 

다음은 코드 흐름에 대한 설명이다.

 

# 1. 초기화 및 입력

            key = 0; //key에 대한 정보, Bit Mask로 처리할 것
            max = 0; //'$'를 몇개 먹는지?
            map = new char[102][102];
            visit = new int[102][102]; //visit를 -1로 초기화

            for(int a=0; a<=r+1; a++)
                for(int b=0; b<=c+1; b++)
                    visit[a][b] = -1;

            for(int a=1; a<=r; a++){
                char[] str = br.readLine().toCharArray();
                for(int b=1; b<=c; b++)
                    map[a][b] = str[b - 1];
            }

            String keys = br.readLine(); //0이 아니면 key에 어떤 키를 갖는지 수정해준다.
            
            if(!keys.equals("0")) {
                char[] keys_ = keys.toCharArray();
                for(int a=0; a<keys_.length; a++)
                    key |= (1 << keys_[a] - 97);
            }
            //keys_[a] - 97 == keys_[a] - 'a'

visit을 -1로 초기화했는데, 만약 visit를 0으로 초기화하면 다음과 같은 반례를 만나게된다.

5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0

 

# 2. BFS

    static void BFS(){

        Queue<Point> Q = new LinkedList<>();

        visit[0][0] = key;
        Q.add(new Point(0, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 0 || nx < 0 || ny > r+1 || nx > c+1 || map[ny][nx] == '*' || visit[ny][nx] == key) continue;

                char c = map[ny][nx];
                visit[ny][nx] = key;

                if(c >= 'A' && c <= 'Z') {
                    if((key & (1 << c - 65) ) == 0) continue; //해당 문에 맞는 열쇠 없으면 skip
                }
                else if(c >= 'a' && c <= 'z') //열쇠를 방문하면 열쇠 추가
                    key |= (1 << c - 97);
                else if(c == '$') //문서를 만났을 때
                    max++;

                map[ny][nx] = '.'; //문/열쇠/문서는 다음에 다시 if문 안에 들어오지 않기 위해 '.'로 변경
                Q.add(new Point(ny, nx));
            }
        }
    }

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
    }
    static char[][] map;
    static int[][] visit;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int max, r, c, key;

    static void BFS(){

        Queue<Point> Q = new LinkedList<>();

        visit[0][0] = key;
        Q.add(new Point(0, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 0 || nx < 0 || ny > r+1 || nx > c+1 || map[ny][nx] == '*' || visit[ny][nx] == key) continue;

                char c = map[ny][nx];
                visit[ny][nx] = key;

                if(c >= 'A' && c <= 'Z') {
                    if((key & (1 << c - 65) ) == 0) continue;
                }
                else if(c >= 'a' && c <= 'z')
                    key |= (1 << c - 97);
                else if(c == '$')
                    max++;

                map[ny][nx] = '.';
                Q.add(new Point(ny, nx));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

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

            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            key = 0;
            max = 0;
            map = new char[102][102];
            visit = new int[102][102];

            for(int a=0; a<=r+1; a++)
                for(int b=0; b<=c+1; b++)
                    visit[a][b] = -1;

            for(int a=1; a<=r; a++){
                char[] str = br.readLine().toCharArray();
                for(int b=1; b<=c; b++)
                    map[a][b] = str[b - 1];
            }

            String keys = br.readLine();
            if(!keys.equals("0")) {
                char[] keys_ = keys.toCharArray();
                for(int a=0; a<keys_.length; a++)
                    key |= (1 << keys_[a] - 97);
            }

            BFS();
            System.out.println(max);
        }
    }
}