91. 퍼즐 달이 차오른다, 가자. (백준 1194) [JAVA]

By howtOLiVeLiKehuman

알고리즘/문제풀이

2021. 5. 29. 00:28

문제

문제 링크 : https://www.acmicpc.net/problem/1194

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

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	8883	3241	2154	33.572%

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
벽 : 절대 이동할 수 없다. (‘#’)
열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

풀이

열쇠를 생각하지 않는다면, 이 문제는 다른 문제들과 동일하게 접근할 수 있다.

이동할 수 있는 방향을 고려하면서 종료위치 1을 최단시간에 접근하기 위해서 BFS를 사용하면 된다.

여기서 문제는 열쇠에 대해 발생한다.

열쇠는 총 6종류가 있고(a~f), 이에 따라 열 수 있는 문도 6종류가 존재한다 (A~F)

이때 열쇠는 중복해서 나올 수 있기 때문에 - 이동하는 노드마다 본인이 가지고 있는 열쇠를 알고 있어야 무분별하게 추가되는 열쇠를 막을 수 있다.

그리고 들고 있는 열쇠의 종류에 따라, 각각의 좌표에 방문한 상태가 다르게 된다.

BFS에서 중복을 방지하기 위하여 이미 방문한 경우는 제외해야 하는데, 지금 들고 있는 열쇠에 따라 이 경우들이 달라질 수 있다는 것이다.

처음에는 HashMap에 단순히 각각의 열쇠를 Set으로 저장해서 체크했다.

하지만 이렇게 할 경우 80% 정도에서 에러가 발생한다. 그 이유는 다음과 같다.

정답으로 가기 위해선 b,c열쇠를 두개 다 들고 있어야 한다.
b만를 들고 해당 지점을 지나간다.
이후 c만 들고 해당 지점을 다른 경우가 지나간다.
그 지점은 b,c 두 열쇠를 가지고 있는게 되어버려 정작 b,c를 모두 가지고 있는 경우에는 지나지 못하게 된다.

그렇다면 결국 각 지점을 지나갈 때, 내가 지금 가지고 있는 열쇠들로 만들 수 있는 부분집합들에 대해서만 못 지나가게 해야한다.

ex) a,b,c 열쇠를 가지고 있으면 -> 0/ a / b / c / ab / ac/ bc / abc

하지만 모든 알파벳에 대해 부분집합을 구현해서 일일히 저장하는 방식은 너무 시간과 메모리를 많이 소요한다.

그래서 생각한 방법이, 각각의 열쇠를 2진수로 생각하는 방식이다. 즉 0 0 0 0 0 0 이 각각 f e d c b a 가 있는지의 여부라 생각한 것이다.

ex) a만 있음 -> 000001 = 2 / f,b있음 ->10010 =34

그리고 해당 지점을 지나간 열쇠들과 AND연산으로 비교해서 본인이 나오게 된다면, 나의 경우를 포함한 경로가 지나갔기 때문에 굳이 체크하지 않아도 된다고 생각한 것이다.

ex) 지나간 열쇠들 (01000, 00100, 01110 ) 나 : 01010 -> (01110&01010) = 01010 / edc 열쇠는 ec를 포함함

이후의 경우에는 각각의 글자를 unicode로 변환하여 생각해서

대문자의 경우는 적당한 수를 빼서 소문자로 만들어주고, 열쇠가 있는지 확인하고

소문자의 경우에는 지나갔는지 확인한 뒤, 내가 열쇠가 없으면 줍는 방식으로 구현하였다.

항상 BFS를 풀 때 생각해야 할 부분은 다음인 것 같다.

중복된 경우인가 (이미 나를 포함한 경우가 지나갔는가)
라운드가 다른 경우 중복이면 굳이 생각할 필요가 없다. (최단거리면 알아서 걔가 먼저 도착)

코드

package algorithm;

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

//# 벽을 절대 x
//. 가능
// 열쇠 a, 문 A
// 현재 위치 0
// 출구 1
// key -> Integer인데, 0 0 0 0 0 0 각각으로 생각
// 0 -> 0, a -> 1, b -> 2, c -> 4, d -> 8, e -> 16, f -> 32

public class Main {
    static int N;
    static int M;

    static Node start;
    static Node end;
    static HashMap<String, Set<Integer>> keySet = new HashMap<>();
    static char[][] map;

    static int[] moveX = {-1,1,0,0};
    static int[] moveY = {0,0,1,-1};

   public static void main(String[] args) throws IOException{
    StringTokenizer st;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    map = new char[N][M];

    for(int i=0; i<N; i++) {
        map[i] = br.readLine().toCharArray();

        for(int j=0; j<M; j++) 
        {
            if(map[i][j] == '0') {
                start = new Node(j,i);
            }
            else if (map[i][j]=='1') {
                end = new Node(j,i);
            }
        }
    }

    int round = 0;
    int size = 0;
    Node cur;
    Queue<Node> q = new LinkedList<>();
    q.add(start);
    check(start.x, start.y, start.keys);

    while(!q.isEmpty()) {
        size = q.size();
        for(int i=0; i<size; i++) {

            cur = q.poll();

            //이동
            for(int a=0; a<4; a++) {
                int nextX = cur.x + moveX[a];
                int nextY = cur.y + moveY[a];

                //범위
                if(nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) {
                    continue;
                }

                char nextpos = map[nextY][nextX];

                //key 97 = a ~ 130 = f
                if((int)nextpos >= 97 && (int)nextpos < 103) {

                    int pos = (int) Math.pow(2, nextpos-97);
                    int newkey = cur.keys;

                    if(check(nextX, nextY, cur.keys)) {    

                        //키 없으면 추가
                        if((cur.keys & pos) == 0) {
                            newkey = cur.keys + pos;
                        }
                        q.add(new Node(nextX, nextY, newkey));
                    }
                }

                //lock 65 = A ~ 71 = B
                else if((int)nextpos >= 65 && (int)nextpos < 71) {

                    int pos = (int) Math.pow(2, nextpos-65);

                    //키 있어야지만 추가
                    if((cur.keys & pos) != 0) {
                        if(check(nextX, nextY, cur.keys)) {
                            q.add(new Node(nextX, nextY, cur.keys));
                        }
                    }
                }

                //종료
                else if(nextpos == '1') {
                    System.out.println(++round);
                    return;
                }

                //이동가능
                else if(nextpos != '#') {
                    if(check(nextX, nextY, cur.keys)) {
                        q.add(new Node(nextX, nextY, cur.keys));
                    }
                }
            }
        }
        round ++;
    }
    System.out.println(-1);
    return;

   }

   static boolean check(int x, int y, int key) {
       String path = x+"-"+y;
       boolean result = true;

       //방문한적이 있으면
       if(keySet.containsKey(path)) {

           Set<Integer> set = keySet.get(path);
           //System.out.println(set + " " + key);
           for(Integer i : set) {
               //해당 키인 애가 한번이라도 왔다 간적이 있으면,
               if( (i & key) == key) {
                   result = false;
               }
           }

           if(result) {
               set.add(key);
           }

       }

       //방문 x
       else {
           Set<Integer> set = new HashSet<Integer>();
           set.add(key);
           keySet.put(path, set);
           result = true;
       }

       return result;
   }
}


class Node{
    public int x;
    public int y;
    public int keys = 0;

    public Node(int a, int b) {
        this.y = b;
        this.x = a;
    }    
    public Node() {}

    public Node(int a, int b, int s) {
        this.y = b;
        this.x = a;
        keys = keys + s;
    }
}

결과

문제