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

🧷 문제 링크

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

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

 

📄 풀이 과정

블로그에서 BFS 의 활용 방법과 이 문제에 대해 정리된 것을 보았다.

• 가장 기초적인 방문체크는 해당 좌표에 이전에 방문한 적이 있는지 확인한다.
• 다음으로 많이 사용되는 것은 특정 시간에 해당 좌표를 방문한 적 있는가
• 이 문제에서는 특정 상태에 해당 좌표를 방문한 적 있는가

어떤 열쇠를 가지고 있는 상태에서 이 지점을 방문했는지 체크하는 것이 이 문제의 핵심이다. 

• 먼저 이 문제에서 키는 a~f 6개 이므로, 각각의 열쇠를 가졌느냐 아니냐로 해서 2^6개의 경우의 수가 나온다.
  따라서 visited[N][M][1<<6] 을 통해 각각의 상태에 방문했을지를 체크해주었다.
• 키의 상태는 2진법으로 나타낼 수 있으며 각 비트는 특정 열쇠를 나타낸다.
  • 오른쪽에서 왼쪽으로 a ~ f의 열쇠를 나타낸다.
  • 000001(2) 열쇠 a를 가지고 있음
  • 100000(2) 열쇠 f를 가지고 있음
• 열쇠에 도달했을 때 해당 키를 추가하려면 | 연산을 사용한다.
  • a열쇠에 도달했을 때 &연산으로 먼저 이미 가지고 있는지 확인한다.
  • 없다면 000001(2)와 현재 열쇠 상태를 | 연산하여 합쳐준다.
• 문에 도달했을 때 해당 키를 가지고 있는지 확인하기 위해서는 & 연산을 사용한다.
  • A문에 도달했을 때 필요한 열쇠는 a이므로 000001(2)와 현재 열쇠 상태를 &연산 했을 때 가지고 있다면 000001(2)를 리턴할 것이다.

(출처 : https://velog.io/@hyeon930/BOJ-1194-%EB%8B%AC%EC%9D%B4-%EC%B0%A8%EC%98%A4%EB%A5%B8%EB%8B%A4-%EA%B0%80%EC%9E%90.-Java)

이 블로그에서 설명이 너무 잘되어 있어서 가지고 왔는데 혹시 문제가 있다면 바로 삭제하겠습니다..ㅜㅜ

 

마지막 부분에서 조금 헤맸다.

현재 가지고 있는 키와 필요한 키를 & 연산한다면, 현재 가지고 있는 키가 나와야 필요한 키가 있는 것이라고 생각했는데, 다시 & 를 찬찬히 생각해보니 만약에 110000 & 000001 한다면 = 000001 이니 필요한 키가 나와야 있는 것이었다. 

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Main_bj_1194_달이차오른다가자 {
    
    static class Point{
        int r, c, k;
 
        public Point(int r, int c, int k) {
            super();
            this.r = r;
            this.c = c;
            this.k = k;
        }
        
    }
 
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input_bj_1194.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        Queue<Point> que = new LinkedList<>();
        boolean[][][] visited = new boolean[N][M][1<<6];     // 2^6개가 필요 (a~f까지 6개의 키가 있을 떄와 없을 때의 경우의 수)
        
        char[][] map = new char[N][M];
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = s.charAt(j);
                if(map[i][j]=='0') {                        // 현재 위치
                    que.offer(new Point(i, j, 0));            // 0개의 열쇠를 가지고 있음
                    visited[i][j][0] = true;
                }
            }
        }
        
        int ans=0;
        boolean ok = false;
        outer: while(!que.isEmpty()) {
            int size = que.size();
            ans++;
            
            for(int i=0; i<size; i++) {
                Point p = que.poll();
                
                for(int d=0; d<4; d++) {
                    int nr = p.r + dr[d];
                    int nc = p.c + dc[d];
                    int nk = p.k;
                    
                    if(nr<0 || nr>=N || nc<0 || nc>=M) continue;
                    if(map[nr][nc]=='#' || visited[nr][nc][nk]) continue;
                    
                    if(map[nr][nc]=='1') {
                        ok = true; break outer;
                    }
                    
                    if(map[nr][nc]>='a' && map[nr][nc]<='z') {
                        int k = 1 << (map[nr][nc]-'a');
                        if((nk & k) != k)    // 현재 키가 없음
                            nk |= k;         // 현재 키를 포함
                    } else if(map[nr][nc] >= 'A' && map[nr][nc] <= 'Z') {
                        int k = 1 << (map[nr][nc] - 'A');    // 현재 문의 키가 있는지를 확인
                        if((nk & k) != k)            // 키가 없음
                            continue;
                    }
                    
                    visited[nr][nc][nk] = true;
                    que.offer(new Point(nr, nc, nk));
                }
            }
        }
        
        if(ok) System.out.println(ans);
        else System.out.println(-1);
        br.close();
    }
 
}
 

 

📌 채점 결과