-
BFS - 백준1194 달이 차오른다,가자 - 장애물 변동에서 탐색 (+테스트케이스 추가)자료구조와 알고리즘/문제풀기 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를 추가할때 순서에 맞춰서 해야해서 하다가 말았다.
- 비트 마스킹을 사용하면, 위와 같은 조합의 수를 쉽게 표현할 수 있다는 사실을 깨달았다. 다음에 또 다른 문제를 만났을 때, 위와 같이 조합들을 쭉 더해서 뭐를 비교하거나, 찾거나 표현할 때 비트마스킹을 떠올려야겠다.
'자료구조와 알고리즘 > 문제풀기' 카테고리의 다른 글
문제 풀이에 자주 사용하는 순열,조합 (0) 2024.05.11 BFS - 백준(1697) 숨바꼭질 - 배열의 인덱스를 이용한 BFS (0) 2024.05.06 BFS - 백준(2178) 미로 찾기 - 4방향 탐색과 BFS (1) 2024.05.06 트리 - 백준(11725) 트리의 부모 찾기 - 트리의 표현과 탐색 (1) 2024.04.28 재귀 - 백준 15657 N과 M(8) - 중복 있는 조합 (1) 2024.04.28