[알고리즘][Python] 백준 2206 벽 부수고 이동하기 문제 풀이

문제 출처 : www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

문제 해석 : 1,1에서 N,M으로 이동하는데 걸리는 최소 거리를 구하는 문제이다. 단 이때 딱 하나의 벽을 부술 수 있으며 도착하지 못하는 경우에는 -1을 출력해야한다.

 

문제 풀이 : BFS문제에 한가지 상태를 고려하는 문제이다. 이 문제를 직접 벽을 제거한 배열을 파라미터로 넘겨줘 풀 수 있지만 시간초과로 인해서 변수 한개를 더 사용해서 이를 풀이하는게 올바르다.

-> visited에 벽을 이미 부쉈을때와 아닌경우를 따로 저장하면서 이를 진행한다.

-> Q에는 벽을 부술수 있는지 없는지 상태를 나타내는 변수를 도입한다.

---

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline

def BFS():
    visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]

    Q = deque()
    Q.append([0,0,1])
    visited[0][0][1] = 1

    while Q:
        x, y, possible = Q.popleft()

        if x == N-1 and y == M-1:
            return visited[x][y][possible]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 1 and possible == 1:
                    visited[nx][ny][0] = visited[x][y][1] + 1
                    Q.append([nx, ny, 0])
                elif visited[nx][ny][possible] == 0 and arr[nx][ny] == 0:
                    Q.append([nx,ny,possible])
                    visited[nx][ny][possible] = visited[x][y][possible] + 1

    return -1

dx = [0,0,1,-1]
dy = [1,-1,0,0]

N, M = map(int, input().split())

arr = []
for _ in range(N):
    arr.append(list(map(int, list(input().rstrip()))))

print(BFS())

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.