[백준] 14442번: 벽 부수고 이동하기 2 - 파이썬
문제보기
https://www.acmicpc.net/problem/14442
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
풀이 및 코드
다른 사람들 코드를 보고 아직 한참 부족함을 느낀 문제다..
(k를 망치의 개수라고 표현하겠다)
필자는 bfs를 활용해 다음과 같은 인사이트를 가지고 문제에 접근했다.
- 특정 좌표에 방문했을 때 보다 망치를 조금 사용하고도 적은 거리로 방문한 적이 있다면 지금의 경로는 최단 경로가 아니다.
풀어서 설명하자면 해당 좌표에 최소 거리로 도착했다고 할지라도 망치를 많이 소비 했다면 앞으로 어떻게 될 지 모르기 때문에 해당 경로가 최단경로임을 확신할 수 없다는 의미이다. 따라서 checked를 3차원 배열로 만들어서 x, y좌표까지 망치 k소지한채로 접근했을 때의 최단 거리를 저장했다.
import sys | |
from collections import deque | |
input = sys.stdin.readline | |
n, m, k = map(int, input().split()) | |
graph = [] | |
for _ in range(n): | |
graph.append(input()[:-1]) | |
# checked[y][x][k] = x, y좌표까지 망치 k소지한채로 접근했을 때의 최소 거리 | |
checked = [[[0 for _ in range(k+1)] for _ in range(m+1)] for _ in range(n+1)] | |
dx = [1, 0, -1, 0] | |
dy = [0, 1, 0, -1] | |
def bfs(k): | |
dq = deque() | |
dq.append([k, 0, 0]) | |
checked[0][0][k] = 1 | |
cnt = 1 | |
if (n, m) == (1, 1): | |
return cnt | |
while dq: | |
cnt += 1 | |
for _ in range(len(dq)): | |
k, y, x = dq.popleft() | |
for d in range(4): | |
ny = y + dy[d] | |
nx = x + dx[d] | |
if ny == n-1 and nx == m-1: | |
return cnt | |
if 0 <= ny < n and 0 <= nx < m: | |
nk = k - int(graph[ny][nx]) | |
# nk = 남은 망치의 개수 | |
if nk < 0: | |
continue | |
# nk보다 망치를 많이 들고도 경로가 적은 값이 있다면 break 없다면 append | |
for i, v in enumerate(checked[ny][nx]): | |
if i >= nk and 0 < v <= cnt: | |
break | |
else: | |
checked[ny][nx][nk] = cnt | |
dq.append([nk, ny, nx]) | |
return -1 | |
print(bfs(k)) |
문제는 풀었지만 상당히 오랜 시간이 걸렸고 썩 좋은 알고리즘은 아니라고 생각되어 다른 사람들의 코드를 살펴보았다.
- 특정 좌표에 접근했을 때 보다 망치를 조금 사용하고도 적은 거리로 도착한 경우가 있다면 지금의 경로는 최단 경로가 아니다.
해당 인사이트는 맞았다. 현재 좌표까지 최소거리가 어떠하든 그것은 기준이 될 수 없다. 왜냐하면 해당 좌표에 최소 거리로 도착했다고 할지라도 망치를 많이 소비 했다면 앞으로 어떻게 될 지 모르기 때문이다. 해당 경로를 계속 진행할지 말지 결정하는 것은 다름아닌 소비한 망치의 개수이다.
bfs의 특성상 먼저 방문할 수록 거리가 더 짧다. 따라서 나중에 방문 할 수록 거리가 늘어난다. 즉 이전에 방문한 것 보다 소비한 망치의 개수가 많다면 해당 경로는 거리도 길고 망치도 많이 사용했기에 최단경로가 아니게 된다. 하지만 망치의 개수가 더 크다면 그것은 어쩌면 최단경로가 될 수도 있다!
따라서 checked를 2차원 배열로 만들어 x, y에 방문했을 때 소비한 망치를 저장해 두고, 방문을 할 때 저장된 값보다 망치를 많이 소비했다면 bfs를 진행하지 않았다. 반대로 보다 망치를 조금 소비했다면 bfs를 진행시켰다.
import sys | |
from collections import deque | |
input = sys.stdin.readline | |
n, m, k = map(int, input().split()) | |
graph = [] | |
for _ in range(n): | |
graph.append(input()[:-1]) | |
# checked[y][x] => y, x까지 오는데 소비한 망치의 개수 | |
checked = [[k+1 for _ in range(m+1)] for _ in range(n+1)] | |
dx = [1, 0, -1, 0] | |
dy = [0, 1, 0, -1] | |
def bfs(k): | |
dq = deque() | |
dq.append((0, 0)) | |
nk = 0 | |
cnt = 1 | |
checked[0][0] = nk | |
while dq: | |
cnt += 1 | |
for _ in range(len(dq)): | |
y, x = dq.popleft() | |
for d in range(4): | |
ny = y + dy[d] | |
nx = x + dx[d] | |
if (ny, nx) == (n-1, m-1): | |
return cnt | |
if 0 <= ny < n and 0 <= nx < m: | |
# 소비한 개수 업데이트 후 기존보다 작은지 체크 | |
nk = checked[y][x] + int(graph[ny][nx]) | |
if nk <= k and nk < checked[ny][nx]: | |
checked[ny][nx] = nk | |
dq.append((ny, nx)) | |
return -1 | |
if (n, m) == (1, 1): | |
print(1) | |
else: | |
print(bfs(k)) |
해당 문제는 solved.ac 기준 골드3에 랭크되어 있다. (3치고는 어렵지 않나?)