[Python] 백준2206 벽 부수고 이동하기

26 Jun 2023 in Study on Algorithm

백준2206 벽 부수고 이동하기 링크

문제

예제 입력

---

코드

import sys
from collections import deque
n, m = map(int, input().split())
arr = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]
visited = [[[-1] * 2 for _ in range(m)] for _ in range(n)]
    
def bfs():
    q = deque()
    q.append([0, 0, 0])
    visited[0][0][0] = 1

    while q:
        x, y, z = q.popleft()

        for dx, dy in [[-1, 0],[1, 0],[0, -1],[0, 1]]:
            newx = x + dx
            newy = y + dy

            if 0 <= newx <  n and 0 <= newy < m:
                # 이미 뚫은 상황이거나 일반적인 상황
                if arr[newx][newy] == 0 and visited[newx][newy][z] == -1:
                    visited[newx][newy][z] = visited[x][y][z] + 1
                    q.append([newx, newy, z])
                # 벽 뚫음
                elif arr[newx][newy] == 1 and visited[newx][newy][z] == -1 and z == 0:
                    visited[newx][newy][1] = visited[x][y][z] + 1
                    q.append([newx, newy, 1])   

bfs()
if visited[-1][-1][0] == -1 and visited[-1][-1][1] != -1:
    print(visited[-1][-1][1])
elif visited[-1][-1][0] != -1 and visited[-1][-1][1] == -1:
    print(visited[-1][-1][0]) 
else: # 둘다 -1이거나 양수
    print(min(visited[-1][-1][0], visited[-1][-1][1]))

설명

파이썬을 통해서 사용자로부터 입력받아 BFS 알고리즘을 사용하여 벽 부수고 이동하기를 구현했습니다.

---

결과