개요
🖱️ 문제 링크 : https://www.acmicpc.net/problem/14442
- 시간 제한 : 2 초
- 메모리 제한 : 512 MB
문제
⌨️ 입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
🖨️ 출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
해결 방법
💡 문제 이해
벽 부수고 이동하기 1 과 달라진 점이 벽을 부술수 있는 개수 를 제외하곤 없다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
그런데 Vscode 에선 테케 전부 통과했는데, BOJ에서는 계속 시간초과가 났다.
디버깅 하면서 알게 된건데
- 빈 칸일 때는 이전에 방문한 적이 있었는데 꼬박꼬박 잘 체크하다가 ㅎㅎ..
- 벽을 만났을 땐 방문 체크를 안하고 있었다.
벽을 뚫고 갈 곳을 이전에 가봤었는지를 체크하지 않아서 중복방문 발생 → 시간초과 가 일어난 것 같다.
# 이전에 벽을 뚫고 갈 곳을 가보았는지 확인 (더 빠르게 방문했던 적이 있다면 그 후의 탐색을 할 필요가 없음)
visited[cnt + 1][nx][ny] == 0벽을 만났을 때 elif문에 이 코드를 추가하니까 정상적으로 정답처리가 됐다.
Python Code
# 백준 14442 벽 부수고 이동하기 2
import sys
from collections import deque
read = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 행렬의 세로, 가로, 벽을 K개 까지 부숴도 됨
N,M,K = map(int, read().split())
matrix = [ list(map(int,read().rstrip())) for _ in range(N) ]
visited = [ [ [0]*M for _ in range(N) ] for _ in range(K+1) ]
def bfs(break_cnt,x,y):
q = deque()
q.append([break_cnt, x, y])
visited[break_cnt][x][y] = 1
while q:
cnt, x, y= q.popleft()
# 출구 도착!
if x == N-1 and y == M-1:
return visited[cnt][x][y]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < M:
# 미 방문 빈 칸이라면 평소대로 지나가고
if matrix[nx][ny] == 0 and visited[cnt][nx][ny] == 0:
visited[cnt][nx][ny] = visited[cnt][x][y] + 1
q.append([cnt,nx,ny])
# 아직 벽을 부술 수 있는 카운트가 남아있고, 내가 벽을 뚫고 갈 곳을 가보았는지 확인 (더 빠르게 방문했던 적이 있다면 그 후의 탐색을 할 필요가 없음).
elif matrix[nx][ny] == 1 and cnt < K and visited[cnt + 1][nx][ny] == 0:
# 벽을 부수고 지나간다
visited[cnt+1][nx][ny] = visited[cnt][x][y] + 1
q.append([cnt+1,nx,ny])
return -1
print(bfs(0,0,0))오늘의 알쓸신잡
💾 메모리초과와 시간초과
그냥 정답처리 받고 남의 코드 구경하다가 발견한건데, 자신의 로직에 확신이 드는데 자꾸 시간초과나 메모리초과가 난다면! (특히 그래프에서)
배열의 차원 순서를 한번 확인 해보는건 어떨까?
이게 뭔 개소린가 하면 그래프 문제에서 방문 체크 배열을 예로 들어보자. (위 문제에서는 visited 배열)
처음에 나는 이렇게 구현했었다. (실제로 이렇게 많이 쓰기도 하고)
visited = [ [ [0]*(K+1) for _ in range(M) ] for _ in range(N) ]다음은 이렇게 선언했고,
visited = [ [ [0]*M for _ in range(N) ] for _ in range(K+1) ]한번 채점 결과를 볼까?
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
배열 선언 한줄 차이로 이정도면 유의미한 차이가 아닐까? 싶어서 좀 더 파봤는데 신기한 걸 알게 됐다.
결론부터 말해주자면
가장 큰 길이의 차원을 가장 오른쪽에 놓는 것이 메모리가 가장 절약 된다는 것!
Ex) visited[1000][1000][11]의 메모리 사용량 > visited[11][1000][1000]의 메모리 사용량
위 문제 같은 경우 K는 커봐야 10, N,M은 1000 이기에 가능했던 거다. 무작정 막 바꾸는게 아니고..
왜 이런일이 생겼냐 하니 공간지역성과 (JAVA 에서는) 헤더의 수 차이 때문이란다.
너무 깊게는 안 들어가고 예시만 들자면
하나는 바로 다음에 확인할 원소가 바로 옆에 있는 반면에, 다른 하나는 아예 다른 배열로 찾아가야 한다고 생각하면 편하다.
실생활의 예로
101호 → 102호 → 103호 → 201호 → … 가 101호 → 201호 → 301호 → 102호 → … 보다 더 빠르다는 것에 의문을 품는 사람은 없을거다.
알아두면 유용하긴 하겠지만 그냥 알아만 두기로 했다. 솔직히 안쓸거 같애..
