https://www.acmicpc.net/problem/2206
진짜 작살나고 짜릿하게 어려웠던 문제다.
매일 실버만 풀다가 처음으로 도전한 골드문제였다.
🥊 골드한테 흠칫 뚜들겨 맞고, 🚑 브론즈 응급실 가서 수액 맞고 겨우 정신차렸다..
알고리즘 고수 멋쟁이(✨)한테 헬프 요청해서 겨우 풀었다 ㅠㅡㅠ
처음에 접근했던 방법은 다음과 같다.
출발지인 (0, 0) 을 방문했다고 체크를 해주고, queue에 (0,0,1,0)를 넣어준다. [ x, y, cnt, check ]
를 넣어준 것이다.
이때 check
는 벽을 부셨는지 안부셨는지 여부를 나타낸다.
cnt
는 한칸씩 이동한 횟수를 나타낸다.
queue에 들어온 좌표의 상하좌우 중 방문 안한 곳만 방문할 것이다.
2-1. 만약 (nx,ny)가 벽이고, 벽을 부신적이 없으면 벽을 부시고 방문해준다.
그리고 queue에 (nx, ny, cnt+1, 1)
을 넣어준다.
2-2. 만약 (nx,ny)가 길이면, queue에 (nx, ny, cnt+1, check)
를 넣어준다.
queue에 들어온 좌표가 도착지이면 cnt를 return 한다.
이렇게 풀었는데 시간초과가 발생했다.
코드 상으로는 다 맞는 것 같은데 무엇이 문제인지 알 수가 없었다.
반례를 계속 찾아보다가 논리의 문제를 알게 되었다.
5 4
0001
1101
0001
0111
0010
위의 예제같은 경우 출발지 (0,0) 에서 바로 밑에 있는 벽을 부시고 이동하는 것이 처음엔 최적의 해다.
그렇지만 나중에 도착지에 가선 벽을 하나 더 부셔야 한다.
따라서 처음에 벽을 부시지않고 옆쪽으로 돌아와서 마지막에 벽을 부셔야 한다.
지금의 코드로는 이러한 상황을 고려할 수 없었다.
따라서 벽을 부셨을 때와 부시지 않았을 때를 분리해서 방문을 체크해야 한다.
기존의 visited[x][y]
를 visited[check][x][y]
로 바꾸어주었다.
벽을 부신 여부에 따라 다른 visited에 저장된다.
visited[check][nx][ny] == 0
만 방문할 것이다.visited[check][nx][ny] = 1
(nx, ny, cnt+1, 1)
을 넣어준다.(nx, ny, cnt+1, check)
를 넣어준다.import sys
from collections import deque
input=sys.stdin.readline
n, m = map(int,input().rstrip().rsplit())
queue = deque()
matrix = []
visited = [[[0]*(m+1) for _ in range(n+1)] for _ in range(2) ]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(n):
row = input().rstrip()
matrix.append(row)
def bfs():
queue.append([0,0,1,0])
while queue:
x,y,cnt,check = queue.popleft()
if x == n-1 and y == m-1:
return cnt
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
# 방문했으면 continue
if visited[check][nx][ny] == 1:
continue
#방문 안했으면
else:
visited[check][nx][ny] = 1
#벽이면
if matrix[nx][ny] == '1':
#벽 부신적이 없으면, 부시고 방문해줘
if check == 0 :
queue.append([nx,ny,cnt+1,1])
#길이면
else:
queue.append([nx,ny,cnt+1,check])
return -1
print(bfs())