백준 #1194 달이 차오른다, 가자

이번 문제는 재미있는 문제였다고 봅니다.  스토리가 있긴 한데요.  난이도는 Gold I입니다.  정답률 25.9%, 정답자 1,001명입니다.

 

한지민이 인생의 미로를 탈출하려고 합니다.  자신이 처해있는 상황을 해결하기 위해서는 탈출구로 탈출해야 합니다.  그런데, 간혹 해결할 수 없는 문제에 도달합니다.  이 문제를 해결하기 위해서는 키를 구해야 하는데, 키는 그 문제에 맞는 키여야 해당 문제를 해결할 수 있습니다.  키는 a~f까지 존재하며, 문제는 A~F까지 존재하고, 각각이 대응되는 키와 문제입니다.  해결할 수 없는 문제는 #입니다.  0은 출발점이고, 1은 새로운 탈출구입니다.  봄이 가기전에 가장 빨리 탈출구로 탈출하려고 합니다.  늙어서 김혜자가 되면 안 되거든요.

 

The Light in Your Eyes (from JTBC)

 

문제는 전형적인 BFS 알고리즘 문제에서 변형이 된 상태입니다.

 

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

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

일반적으로 BFS로 문제를 해결할 때에는 노드의 방문 여부를 표시합니다.  그런데 이 문제에는 키라는 상태가 하나 더 추가됩니다.  그래서 키와 지도상 위치를 같이 visit에서 처리해야 합니다.  같은 지도상 위치라도 키를 어떤 것을 가지고 있느냐에 따라서 달라집니다.

 

또한 문제는 상태값과 함께 큐에 넣는 값도 같이 보내주어야 합니다.  보통 큐에는 지도상 위치만 같이 넣어주었었는데, 그걸로 매핑하기가 힘듭니다.  키 6개, 위치정보 2,500이니까, 15,000 정도의 공간만 확보해주면 됩니다.  거기에 얼마나 지도상에서 헤매었는가에 대한 정보를 같이 기록해주어야 합니다.  이 정보는 꽤 길 수 있습니다.  그래보았자 이것도 최대 15,000정도이니까, 그정도를 넣을 수 있는 자료구조가 필요합니다.  그래서 총 상태를 저장하는데, int 자료형만으로는 해결이 어렵습니다.

 

다양한 예제입니다.

5 10
...#a#....
####.#####
.b..0.AB.1
##########
..........
    
ans = 15

4 7
1FD...f
AC....a
#.....#
cd....0
    
ans = 17

11 10
b#..0CBA#c
.#.####1#.
.#..#a###.
.##.#B#...
.#....#.##
.#.####...
.#..#...##
.##.###B##
.#........
.#######..
..........

ans = 108