본문 바로가기

Problem Solving/BOJ-Gold

(Python) 백준 2206 - 벽 부수고 이동하기

반응형

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)
반응형