2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로��
www.acmicpc.net
방문을 체크하는 ck배열을 삼중배열로 만들어서 벽을 안부술경우 / 부술경우를 구별한다
벽을 안부쉈다면 ck[x][y][0]에 거리를 저장하고, 부쉈다면 ck[x][y][1]에 거리를 저장한다
그리고 n, m까지 갔다면 저장했던 거리를 리턴, 아니라면 -1을 리턴해 출력해준다
from collections import deque
dx, dy = [0, -1, 0, 1], [-1, 0, 1, 0]
def sol():
ck = [[[0]*2 for _ in range(M)] for _ in range(N)]
ck[0][0][0] = 1
while q:
x, y, wall = q.popleft()
if x==(N-1) and y==(M-1): return ck[x][y][wall]
for i in range(4):
if 0 <= x+dx[i] < N and 0 <= y+dy[i] < M and ck[x+dx[i]][y+dy[i]][wall] == 0:
if Map[x+dx[i]][y+dy[i]]=='0':
ck[x+dx[i]][y+dy[i]][wall] = ck[x][y][wall] + 1
q.append([x+dx[i], y+dy[i], wall])
if wall == 0 and Map[x+dx[i]][y+dy[i]] == '1':
ck[x+dx[i]][y+dy[i]][1] = ck[x][y][0] + 1
q.append([x+dx[i], y+dy[i], 1])
return -1
N, M = map(int, input().split())
Map = [list(input()) for _ in range(N)]
q = deque()
q.append([0, 0, 0])
print(sol())
'알고리즘 > 백준 (Pyhthon)' 카테고리의 다른 글
[알고리즘] 백준 15988 1, 2, 3 더하기 2 / 파이썬 (0) | 2020.09.22 |
---|---|
[알고리즘] 백준 3495 아스키 도형 / 파이썬 (0) | 2020.09.22 |
[알고리즘] 백준 11779 최소비용 / 파이썬 (0) | 2020.09.21 |
[알고리즘] 백준 15685 드래곤 커브 / 파이썬 (0) | 2020.09.17 |
[알고리즘] 백준 16197 두 동전 / 파이썬 (0) | 2020.09.17 |