[백준]16933 : 벽부수고 이동하기3

BFS

문제 : 벽 부수고 이동하기3

이 문제도 1, 2와 같은 BFS 문제입니다.
이 문제의 이전과의 차이점은
이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.

낮과 밤이 존재하고, 낮에만 벽돌을 부술 수 있다는 조건이 추가된다는 것입니다.(문제 조건 구현하는 것이 꽤 까다로운 문제였습니다.)

저번 문제와의 구현방식 차이점은 저번 방식은 k개 부터 거꾸로 뺐다면 이번 문제는 하나씩 더하면서 구현했습니다.
먼저, 다음 칸이 벽이 있는지 없는지로 먼저 구분하고
벽이 있으면, 벽을 부술 수 있는지 확인하고, 낮인지 밤인지 확인합니다.
여기서 낮과 밤을 구분할 때 visited[x][y][v] % 2 == 1:
나머지 연산을 이용했습니다. (처음엔 무조건 1이고 이동할 때 마다(자리에 머무르는 경우에도) 1씩 더해지기 때문에 나머지 연산을 통해 낮과 밤을 구분할 수 있습니다. )
벽이 없으면, 자유롭게 이동해줍니다.

여기서 체크해야할 것은,
1. nx, ny 가 인덱스를 넘어가는지 확인
2. nv가 k를 넘어가는지 확인
3. visited[nx][ny][nv]가 최단거리인지 확인
사실상 3번을 구현을 안하면 틀리는 문제였습니다.

import sys
from collections import deque
input = sys.stdin.readline
n, m, k = map(int, input().split())
lst= []
INF = int(1e9)
for i in range(n):
	lst.append(list(map(int, sys.stdin.readline().rstrip())))
# 결과 리스트 
visited = [[[0]*(11) for _ in range(1001)] for _ in range(1001)]
# 첫시작은 [0, 0, 0 ]
visited[0][0][0] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
	ret = INF
	q = deque()
	q.append((0, 0, 0))
	while q:
		x, y, v = q.popleft()
        	# 벽을 조금만 깨는 것이 최단거리일 수도 있으므로 비교 
		if x == n-1 and y == m-1:
			ret = min(ret, visited[x][y][v])
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m :continue
            		# 벽이 있으면 벽을 추가 아니면 그대로 
			nv = v+1 if lst[nx][ny] == 1 else v
            		# pypy는 c++과 다르게 여기서 가지치기 안하면 시간초과 
			if nv > k : continue
            		# 최단 거리 인지 확인 
			if visited[nx][ny][nv] and (visited[nx][ny][nv] <= visited[x][y][v]+1): continue
			# 벽이 있는지
			if lst[nx][ny] == 1:
            			# 벽을 부술 수 있는지 확인
				if nv > k :continue
                		# 낮이면 
				if visited[x][y][v] % 2 == 1:
					visited[nx][ny][nv] = visited[x][y][v]+1
                		#밤이면 기다려야지 뭐,,    
				else:
					visited[nx][ny][nv] = visited[x][y][v]+2
            		# 벽이 없으면 자유롭게 깨자        
			else:
				visited[nx][ny][nv] = visited[x][y][v]+1
            		# 여기서 한번에 넣어주기 위해 nv 만듦
			q.append((nx, ny, nv))
   	 # ret 값이 INF 면 -1 아니면 ret 출력
	answer = -1 if ret == INF else ret
	return answer
print(bfs())