파이썬(python) 백준 2206 : 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

문제 내용

시간 제한 : 2 초

메모리 : 192 MB

 

N×M의 행렬로 표현되는 맵에서 (1, 1)에서 (N, M)로 이동할때 최단 경로로 이동

이동은 4방향이다. 시작, 끝점 카운트해서 최단경로 길이 구하라.

이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동해도 됨

• 0은 이동할 수 있는 곳
• 1은 이동할 수 없는 벽이 있는 곳

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다.

다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

(1, 1)과 (N, M)은 항상 0이라고 가정하자.

 

출력

최단거리 출력. 불가능하면 -1

 

예제 입력 1

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

 

예제 출력 1 

29

유형

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

풀이

최단경로를 구하는 문제이므로 DFS와 BFS 를 생각해낼 수 있는데

가중치가 없는 최단경로 문제이므로 이 문제는 BFS 문제다.

또한 최단거리를 구해야 하므로 visited 배열에 방문여부가 아닌 최단길이를 갱신해나간다.

여기까지는 평범한데 이 문제는 갈 수 없는 곳을 1회 지나갈 수 있으므로 추가적인 처리가 필요하다.

 

1) 진행 상황에 내가 벽을 부쉈는지 안부쉈는지 여부를 추가해줘야 한다

(x위치, y위치, 현재경로길이, 벽을 부쉈는지 여부(True/False)

 

2) 벽을 부수고 지나가는 경우와 벽을 부수지 않은 경우가 같은 배열에 기록되면 혼란이 오므로 분리해야 한다.

아래의 예시를 보자.
벽을 부수고 지나간 경우가 더 빠르다고 기록했었는데 알고보니 그 끝에 막다른 길이 있었고
부수지 않은 경우가 처음엔 느리지만 마지막에 벽을 뚫어서 도착지에 도달할 수 있다.

만약 같은 배열에 쓰면 엉망이 되어버릴 것이다.

01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

 

그러므로 아래와 같이 배열을 분리하여 각각 다르게 진행시키면 해결된다.

1. 벽을 안부순 경우의 최단경로 저장 배열
2. 벽을 부순 경우의 최단경로 저장 배열

import sys
import collections
n,m= map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().rstrip() for _ in range(n)]
move_arr = [[[int(1e9)]*m for _ in range(n)] for _ in range(2)]
dx = [1,-1,0,0]
dy = [0,0,-1,1]
min_day = 999999

q = collections.deque([(0,0,1,False)])
move_arr[0][0][0] = 1
move_arr[1][0][0] = 1

while q:
    cur = q.popleft()
    if cur[0]==n-1 and cur[1]==m-1:
        min_day = min(min_day, cur[2])
    for i in range(4):
        xx = dx[i]+cur[0]
        yy = dy[i]+cur[1]
        if xx >=0 and yy>=0 and xx<n and yy<m:
            next_day = cur[2]+1
            broken = cur[3]
            if  board[xx][yy] == '0':
                if move_arr[broken][xx][yy] > next_day:
                    move_arr[broken][xx][yy] = next_day
                    q.append((xx,yy,next_day,broken))
            else:
                if broken == False and move_arr[1][xx][yy] > next_day:
                    move_arr[1][xx][yy] = next_day
                    q.append((xx,yy,next_day, True))

if min_day == 999999:
    print(-1)
else:
    print(min_day)