반응형
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
아이디어
- 가중치가 없는 그래프의 최단경로 찾기 문제이므로 BFS를 사용한다.
- 방문여부를 체크할 때, 벽을 부순 이후랑 이전을 구분해서 체크해준다.
코드
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[input().strip() for _ in range(n)]
# 각 칸의 왼쪽은 벽을 부수지 않았을 때, 오른쪽은 벽을 부쉈을 때 방문 여부
v=[[[0,0] for _ in range(m)] for _ in range(n)]
dy,dx=[1,-1,0,0],[0,0,1,-1]
q=deque([(0,0,0)])
# 목적지에 도달했는지 체크
f=0
while q:
y,x,b=q.popleft() # y좌표, x좌표, 벽 파괴 여부
if (y,x)==(n-1,m-1): f=1; break
for i in range(4):
ny,nx=y+dy[i],x+dx[i]
if not (0<=ny<n and 0<=nx<m): continue
if a[ny][nx]=='0' and not v[ny][nx][b]:
v[ny][nx][b]=v[y][x][b]+1
q.append((ny,nx,b))
# 아직 벽을 파괴하지 않았고, 인접 칸이 벽이고, 벽을 부순 상태로 해당 칸을 방문한 적이 없을 시
elif a[ny][nx]=='1' and not v[ny][nx][1] and b<1:
v[ny][nx][1]=v[y][x][f]+1
q.append((ny,nx,1))
print(v[y][x][b]+1 if f else -1)
반응형
'Problem Solving > BOJ-Gold' 카테고리의 다른 글
(Python) 백준 5430 - AC (1) | 2023.11.27 |
---|---|
(Python) 백준 11758 - CCW (0) | 2023.11.14 |
(Python) 백준 10282 - 해킹 (1) | 2023.11.04 |
(Python) 백준 1016 - 제곱 ㄴㄴ 수 (0) | 2023.10.31 |
(Python) 백준 1600 - 말이 되고픈 원숭이 (0) | 2023.10.30 |