자료구조와 알고리즘/문제풀기

BFS - 백준1194 달이 차오른다,가자 - 장애물 변동에서 탐색 (+테스트케이스 추가)

now0204 2024. 5. 11. 00:12

달이 차오른다, 가자. 

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB 18189 7592 5153 38.747%

문제

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

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

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

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

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

  • 빈 칸: 언제나 이동할 수 있다. ('.')
  • 벽: 절대 이동할 수 없다. ('#')
  • 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
  • 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
  • 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
  • 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

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

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

입력

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

출력

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

예제 입력 1 복사

1 7
f0.F..1

예제 출력 1 복사

7

예제 입력 2 복사

5 5
....1
#1###
.1.#0
....A
.1.#.

예제 출력 2 복사

-1

예제 입력 3 복사

7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

예제 출력 3 복사

55

예제 입력 4 복사

3 4
1..0
###.
1...

예제 출력 4 복사

3

예제 입력 5 복사

3 5
..0..
.###.
..1.A

예제 출력 5 복사

6

예제 입력 6 복사

4 5
0....
.#B#A
.#.#.
b#a#1

예제 출력 6 복사

19

예제 입력 7 복사

1 11
c.0.C.C.C.1

예제 출력 7 복사

12

예제 입력 8 복사

3 6
###...
#0A.1a
###...

예제 출력 8 복사

-1

 

 

- 추가 테스트 케이스 (질문 게시판 -rebas님 공유)

3 7
f0.F...
aF....A
b....B1
Answer: 9


3 7
f0.F...
a#....B
#bA..B1
Answer: 13


3 7
f0.F...
a###.#B
#bA..C1
Answer: 21


8 6
######
#0...#
####.#
#....A
a.###.
#.###.
#C#.#.
#1###c
Answer: 32


4 4
####
#0.#
#..#
#.#1
Answer: -1


5 5
aa#..
.0#..
a##..
....#
...A1
Answer: 8


8 6
abcdef
......
......
.....0
#####.
ABCDEF
.#####
.....1
Answer: 30


2 3
0A.
a#1
Answer: 5


3 3
1a1
#0#
1A1
Answer: 2


10 5
#a##1
#B##A
.....
####.
.....
C####
.....
##.#.
...#.
c##b0
Answer: 39



10 5
#1##1
#B##A
.....
####.
.....
C####
.....
##c#.
...#.
a##b0
Answer: 24



5 7
f0aF...
###.#bA
###c##.
#d#D##.
1..C..B
Answer: 21



6 6
#1FFFF
f####.
A####a
.####b
B..0#.
......
Answer: 36



8 11
###########
1..........
##########.
...........
.#####A####
.aB........
##########.
b.........0
Answer: 54



5 11
1AaAaAaAaA1
...........
a#########A
B#########b
.....0.....
Answer: 21



4 4
ab#.
A0A.
..#1
...B
Answer: 7



50 50
##################################################
.................................................1
.#################################################
..................................................
########################################F########.
..................................................
.#################################################
..................................................
#####################f###########################.
..................................................
.#################################################
.#################################################
..................................................
#################################################E
..................................................
e#################################################
..................................................
#################################################.
..................................................
.#################################################
.#################################################
..................................................
D################################################.
..................................................
.#################################################
..................................................
#################################################.
....................................C.............
.###################################d#############
.######################c##########################
..................................................
#################################################.
..................................................
.#################################################
..................................................
#################################################.
..................................................
.#######################B#########################
.#######################B#########################
..................................................
#################################################.
..................................................
.#################################################
...................AbA............................
#################################################.
..................................................
.#################################################
.################################################0
..................................................
a#################################################
Answer: 912
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n,m;
    static char[][] maze;
    static int[][][] distance;
    static int[] dr ={-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static final int DOOR = 1;
    static final int KEY = 2;
    static final int EXIT =3;
    static final int WALL = 4;
    static final int NONE = 5;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        maze = new char[n][m];
        distance = new int[n][m][1<<6];
        Queue<Point> q = new LinkedList<>();

        for(int i=0;i<n;i++){
            String input =sc.next();
            for(int j=0; j<m;j++){
                char ch = input.charAt(j);
                if(ch == '0'){
                    q.offer(new Point(i,j,0));
                    distance[i][j][0] = 1;
                }
                maze[i][j] = input.charAt(j);
            }
        }

        while (!q.isEmpty()){

            Point now = q.poll();


            for(int i=0; i<4; i++){
                int nr = now.r+dr[i];
                int nc = now.c+dc[i];
                if(nr <0 || nr >=n || nc <0 || nc >=m) continue;

                int next = maze[nr][nc];

                switch (getType(next)){
                    case WALL->{
                        continue;
                    }
                    case NONE->{
                        if(distance[nr][nc][now.key] == 0){
                            distance[nr][nc][now.key] = distance[now.r][now.c][now.key]+1;
                            q.offer(new Point(nr,nc,now.key));
                        }
                    }
                    case KEY ->{
                       int nextKey = now.key | 1<<(next-'a');
                       if(distance[nr][nc][nextKey] == 0){
                           distance[nr][nc][nextKey] = distance[now.r][now.c][now.key]+1;
                            q.offer(new Point(nr,nc,nextKey));
                       }
                    }
                    case DOOR -> {
                        next -= 'A';
                        //key를 가지고 있으면,
                        if((1<<next & now.key) == 0)continue;
                        if(distance[nr][nc][now.key] == 0) {
                            distance[nr][nc][now.key] = distance[now.r][now.c][now.key] + 1;
                            q.offer(new Point(nr, nc, now.key));
                        }
                    }
                    case EXIT -> {
                        System.out.println(distance[now.r][now.c][now.key]);
                        return;
                    }
                }


            }


        }

        System.out.println(-1);

    }

    static int getType(int c){
        if (c == '#') return WALL;
        else if (c == '.' || c == '0') return NONE;
        else if (c >= 'a' && c <= 'f') return KEY;
        else if (c >= 'A' && c <= 'F') return DOOR;
        else if (c == '1') return EXIT;
        else return -1;
    }

   static class Point{
        int r,c,key;
        public Point(int r, int c, int k){
            this.r = r;
            this.c = c;
            this.key =k;
        }
    }

}

 

 

  • 비트마스킹 + BFS 조합으로 풀 수 있는 문제이다.
  • KEY 묶음의 조합에 따라 갈 수 있거나, 없거나를 결정해야한다.
  • KEY 묶음 조합을 표현하기 위해 비트마스킹을 사용한다 
  • 000000 6개의 비트로 000001 ->a, 000010 ->b ... > 111111 ->abcdef 
  • 중간에 문을 만났을 때 
    • 가지고 있는 key꾸러미 비트 & 1 << 문알파벳 - 'A' 를 비교해서 KEY가 있는지 아닌지 판단
    • &연산을 사용하면, 양쪽이 1일때만 비트가 1로 올라가는 것을 이용한 것이다.  
  • 중간에 키를 만났을 때 
    • 가지고 있는 key꾸러미 비트 | 1<< 키알파벳 - 'a'를 수행한다. 
    • |연산을 사용하면, 둘 중 한 비트만 1이어도 비트가 1로 올라간다. 
    • 따라서 key꾸러미에 해당 키가 이미 있거나 없가나 상관없이 연산 가능하다! 

 

  • 배운점
    • 문제를 보고, key꾸러미 마다 다르게 표현해줘야함을 깨닫고, 키 갯수에 맞는 6C1+6C2+....+6C6을 하려고했다.
    • 이를 표현하려고 각 key의 조합의 수와 해당 알파벳을 Map에 저장해서 풀려고했는데, 중간에 key를 통해 조합을 꺼내는 건 문제가 안되지만, 중간에 key를 추가할때 순서에 맞춰서 해야해서 하다가 말았다. 
    • 비트 마스킹을 사용하면, 위와 같은 조합의 수를 쉽게 표현할 수 있다는 사실을 깨달았다. 다음에 또 다른 문제를 만났을 때, 위와 같이 조합들을 쭉 더해서 뭐를 비교하거나, 찾거나 표현할 때 비트마스킹을 떠올려야겠다.