[자바] 백준 1194 - 달이 차오른다, 가자. (java)

 

목차

 

문제 : boj1194

---

 

필요 알고리즘

• BFS (너비우선 탐색)
  
  • 최단거리를 찾는 문제로 BFS로 풀 수 있다.
• 비트마스킹
  
  • BFS 진행 시 모든 경우에 대해 방문체크가 가능해야한다. 이걸 위해 비트마스킹을 사용한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  BFS를 모른다면 우선 'BFS 알고리즘 (너비 우선 탐색)'을 보자. 특히 이 문제를 풀기 위해서는 '방문체크에 대해 좀 더 써봄' 부분에 적어놓은걸 이해해야 한다.

 

  이 문제의 경우 새로운 열쇠를 먹은 경우, 기존에 갔던 곳을 다시갈 수 있어야 한다. 예를들어 이하의 예시의 경우 0에서 좌측으로가서 a를 먹은 후, 다시 0이 있던 자리로 돌아갈 수 있어야 1까지 도달 가능하다.

1 4
a0A1

 

  결국엔, 방문체크를 모든 경우를 나타낼 수 있도록 만들수만 있다면 단순 BFS로 풀 수 있는 문제이다. 이 문제의 경우 열쇠를 기준으로 방문체크를 초기화해야 하므로, 새로운 열쇠를 찾았을 때를 기준으로 3차원으로 BFS를 진행하면 된다.

방문체크 v[a][r][c]는 a의 열쇠를 가진 상태로 (r,  c)에 방문했음을 나타낸다.

 

  여기서 a는 열쇠가 총 6개이므로 문자열로 처리해도 되지만(예를들어 "110000"이면 a랑 b 열쇠를 가지고 있게), 그 경우 HashMap 등으로 처리해야하므로 3차원 배열로 간단히 처리하려면 비트마스킹을 사용해주면 된다. 이하 코드의 경우, 000000과 같이 6비트가 있다고 했을 때 우측부터 차례대로 a,b,c,d,e,f 열쇠가 있음을 나타낸다. 예를들어 a와 c 열쇠를 가진 상태인 경우 비트로 000101 이 된다.

 

---

 

코드 : github

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

class Pos {
    int r, c, dist, key;
    public Pos(int r, int c, int dist, int key) {
        this.r = r;
        this.c = c;
        this.dist = dist;
        this.key = key;
    }
}

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, 1, -1, 0};
    private static final int INF = 2<<6 + 2;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        char[][] map = new char[r][c];
        Pos start = null;
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                char cur = row.charAt(j);
                if (cur == '0') start = new Pos(i, j, 0, 0);
                map[i][j] = cur;
            }
        }

        boolean[][][] v = new boolean[64][r][c];
        Queue<Pos> q = new ArrayDeque<>();

        int[] qNum = new int[64];
        Arrays.fill(qNum, -1);
        qNum[0] = 0;
        q.add(start);
        v[0][start.r][start.c] = true;

        while (!q.isEmpty()) {
            Pos cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur.r + DR[d];
                int nc = cur.c + DC[d];
                int dist = cur.dist + 1;
                int key = cur.key;

                if (nr<0 || nr>=r || nc<0 || nc>=c || v[key][nr][nc] || map[nr][nc]=='#') continue;
                if (map[nr][nc] == '1') {
                    System.out.println(dist);
                    return;
                }
                v[key][nr][nc] = true;

                char curMap = map[nr][nc];
                if (curMap >= 'a' && curMap <= 'f') {
                    int keyNum = curMap-'a';
                    if ((key & (1<<keyNum)) == 0) {
                        q.add(new Pos(nr, nc, dist, key));
                        key |= 1<<keyNum;
                        v[key][nr][nc] = true;
                        q.add(new Pos(nr, nc, dist, key));
                        continue;
                    }
                }
                if (curMap >= 'A' && curMap <= 'F' && (key & (1<<(curMap-'A'))) == 0) {
                    continue;
                }
                q.add(new Pos(nr, nc, dist, key));
            }

        }

        System.out.println(-1);
    }
}