[BOJ] 1194번 : 달이 차오른다, 가자.

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

접근 방법

처음 문제를 봤을 때 먼저 DFS, BFS 로 탐색을 해야한다는 것은 생각이 남

나는 BFS 탐색으로 했다.

가지고 있는 열쇠를 어떻게 표현해야 될 지에 대한 고민이 생김.

BitMask 사용 ( a 열쇠를 가지고 있음 → 1<<a || b 열쇠를 가지고 있음 → 1<<b)

문제 코드화

Vertex : 가지고 있는 열쇠 + 현재의 위치 (x, y)

• 코드 구현

    class Location{
        int x,y,bit;
        Location(int x,int y,int bit){
            this.x = x;
            this.y = y;
            this.bit = bit;
        }
    }

Edge : 문에 대한 열쇠 Have || 빈 공간 ( . ) 에 대해 상하좌우

• 코드 구현

    if(visit[nx][ny][bit] == 0){
                        // 그냥 빈 곳 이라면
                        if(map[nx][ny]=='.'){
                            visit[nx][ny][bit] = visit[x][y][bit]+1;
                            map[nx][ny] = '.';
                            queue.add(new Location(nx,ny,bit));
                        }
  
                        // 열쇠 or 문
                        else{
                            // 소문자 경우
                            if(map[nx][ny] >= 'a'){
                                // 몇번 째 키 add
                                int newBit = bit|(1<<(map[nx][ny] - 'a'));
                                visit[nx][ny][newBit] = visit[x][y][bit]+1;
                                queue.add(new Location(nx,ny,newBit));
                            }else{
                                // 몇번 째 키 need
                                int newBit = bit&(1<<(map[nx][ny] - 'A'));
                                // 키가 존재 한다.
                                if(newBit != 0){
                                    visit[nx][ny][bit] = visit[x][y][bit]+1;
                                    queue.add(new Location(nx,ny,bit));
                                }// 없으면 그냥 아무 것도 안해 주면 됨.
                            }
                        }
                    }

주의 할점

문제에서 잘 읽어보면 출구 ( 1 ) 이 한 개가 아니다.

Need Know

1. BFS or DFS
2. BitMask ( 몰라도 상관 없긴 하다. F면 100000 을 그냥 내가 직접 넣으면 되기 때문이지만.. 코드가 너무 지저분 할 것 같으니 알아두는게 좋다.)

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static char[][] map;
    static int[][][] visit;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static Queue<Location> queue;
    public static void main(String[] args) throws NumberFormatException, IOException {
        set();
        bw.write(solve()+"");

        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        queue = new LinkedList<>();
        visit = new int[N][M][1<<5+1];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int k=0; k<M; k++){
                map[i][k] = str.charAt(k);
                if(map[i][k]=='0') {
                    map[i][k] = '.';
                    queue.add(new Location(i,k,0));
                }
            }
        }
    }

    static int solve(){
        while(!queue.isEmpty()){
            Location nowLoc = queue.poll();
            int x = nowLoc.x, y = nowLoc.y, bit = nowLoc.bit;
            // 수평&수직 이동
            for(int i=0; i<4; i++){
                int nx = x+dx[i], ny = y+dy[i];
                if(nx>=N || ny>=M || nx<0 || ny<0 || map[nx][ny]=='#') continue;
                // 출구에 도착할 경우
                if(map[nx][ny]=='1'){
                    return visit[x][y][bit]+1;
                }
                if(visit[nx][ny][bit] == 0){
                    // 그냥 빈 곳 이라면
                    if(map[nx][ny]=='.'){
                        visit[nx][ny][bit] = visit[x][y][bit]+1;
                        map[nx][ny] = '.';
                        queue.add(new Location(nx,ny,bit));
                    }

                    // 열쇠 or 문
                    else{
                        // 소문자 경우
                        if(map[nx][ny] >= 'a'){
                            // 몇번 째 키 add
                            int newBit = bit|(1<<(map[nx][ny] - 'a'));
                            visit[nx][ny][newBit] = visit[x][y][bit]+1;
                            queue.add(new Location(nx,ny,newBit));
                        }else{
                            // 몇번 째 키 need
                            int newBit = bit&(1<<(map[nx][ny] - 'A'));
                            // 키가 존재 한다.
                            if(newBit != 0){
                                visit[nx][ny][bit] = visit[x][y][bit]+1;
                                queue.add(new Location(nx,ny,bit));
                            }// 없으면 그냥 아무 것도 안해 주면 됨.
                        }
                    }
                }
            }
        }
        return -1;
    }
}
class Location{
    int x,y,bit;
    Location(int x,int y,int bit){
        this.x = x;
        this.y = y;
        this.bit = bit;
    }
}