문제 출처 : https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
문제
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 칸: 언제나 이동할 수 있다. ('.')
- 벽: 절대 이동할 수 없다. ('#')
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
알고리즘 분류
풀이
전체적인 풀이는, bfs를 이용해, 이동할 수 있는 칸을 이동하며 도착지에 도달하는 최소 거리를 구하는 것이다.
이동 불가한 벽, 그래프를 이탈할 때, 도착지에 도착할 때 등은 여느 bfs문제와 동일하지만,
6개의 키와 문이라는 조건이 붙는다.
이 조건을 구현하기 위해선, 3차원 배열의 visited가 필요하고,
이 visited에는 현재 노드에 열쇠를 어떤 걸 가진 상태로 방문했는지가 저장된다.
처음엔 열쇠를 먹은 개수마다 visited를 달리하고, 큐의 한 요소마다 BooleanArray(6)으로 먹은 열쇠를 저장하였다.
하지만, 열쇠를 먹은 개수로만 visited를 달리하면, a,c 열쇠를 먹었을 때, b,d 열쇠를 먹었을 때 같은 visited(방문 상태)를 공유하게 된다.
따라서 비트 마스킹을 적용하는 것이 정해이다.
비트 마스킹을 처음으로 제대로 적용한 문제인데, 어렵지 않다.
1 shl 7 (1 << 7)을 하게 되면,
2진법으로 나타냈을 때, 1 0 0 0 0 0 0 0 (128) 가 된다.
이때 0 0 0 0 0 0 은 열쇠를 먹은 상태를 저장할 비트들을 의미하며,
왼쪽부터 순서대로 f e d c b a 이다.
따라서 visited[128][n][m]의 배열에는, 모든 열쇠 상태에 대한 그래프의 방문 상태를 저장할 수 있다.
초깃값인 열쇠를 안 먹은 상태는
0 0 0 0 0 0 0 1 (1) 로 표현한다.
여기서 만약 c 열쇠를 먹었다면,
1 | (1 << 3)을 실행하면
0 0 0 0 1 0 0 1로 표시된다.
열쇠를 먹었을 때는 현재 키값에 or 연산을 취하여 갱신하고,
문을 만났을 때는 현재 키값에 and 연산을 취하여 문에 해당하는 키를 가지고 있는지 검사한다.
코드
import java.util.*
val dir = arrayOf(arrayOf(1,0),arrayOf(0,1),arrayOf(-1,0),arrayOf(0,-1))
val visited = Array(1 shl 7){Array(50){BooleanArray(50)} }
data class Node(var r: Int, var c : Int,var key : Int, var dis : Int)
fun bfs(sr : Int, sc : Int, n : Int, m : Int, graph : Array<CharArray>) : Int {
val q: Queue<Node> = LinkedList<Node>()
q.add(Node(sr, sc, 1, 0))
visited[1][sr][sc] = true
while (q.isNotEmpty()) {
val cur = q.poll()
for (i in 0 until 4) {
val nr = cur.r + dir[i][0]
val nc = cur.c + dir[i][1]
var nk = cur.key
if (nr !in 0 until n || nc !in 0 until m) continue
if (visited[nk][nr][nc]) continue
if (graph[nr][nc] == '#') continue
if (graph[nr][nc] == '1') {
return cur.dis + 1
}
//문
if (graph[nr][nc] >= 'A' && graph[nr][nc] <= 'F') {
if (nk and (1 shl (graph[nr][nc]-'A'+1)) != 0) {
q.add(Node(nr, nc, nk, cur.dis + 1))
visited[nk][nr][nc] = true
} else {
continue
}
}
//열쇠
else if (graph[nr][nc] >= 'a' && graph[nr][nc] <= 'f') {
nk = nk or (1 shl (graph[nr][nc]-'a'+1))
q.add(Node(nr, nc, nk, cur.dis + 1))
visited[nk][nr][nc] = true
}
//.
else {
q.add(Node(nr, nc, nk, cur.dis + 1))
visited[nk][nr][nc] = true
}
}
}
return -1
}
fun main() = with(System.out.bufferedWriter()){
val br = System.`in`.bufferedReader()
val (n,m) = br.readLine().split(' ').map{it.toInt()}
var sr=0
var sc=0
val graph = Array(n){r->
val sen = br.readLine()
CharArray(m){c->
var ch= sen[c]
if(sen[c]=='0'){
sr=r
sc=c
ch = '.'
}
ch
}
}
write("${ bfs(sr, sc,n,m, graph) }")
close()
}
댓글