본문 바로가기
알고리즘 문제 풀이

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

by 로널드 피셔 2023. 1. 19.

출처 : https://www.acmicpc.net/problem/2206

from collections import deque

# n : 행 개수 , m :열 개수
n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]

# visited[0][x][y] : 벽을 안 부수고 (x, y)까지 최단거리
# visited[1][x][y] : 벽을 1회 부수고 (x, y)까지 최단거리
visited = [[[0] * m for _ in range(n)] for _ in range(2)]

def bfs(start_x, start_y) :
    visited[0][start_x][start_y] = 1
    move =[(0, 1), (0, -1), (1, 0), (-1, 0)]
    to_visit = deque([(start_x, start_y, 0)])
    while to_visit :
        # z : (x, y)까지 오면서 벽을 부순 적이 있는지 저장 (0 : 안 부숨, 1 : 부숨)
        x, y, z = to_visit.popleft()
        if x == n - 1 and y == m - 1 :
            return visited[z][x][y]
        for dx, dy in move :
            nx = x + dx
            ny = y + dy
            # 범위 벗어나면 방문하지 않음
            if nx < 0 or nx >= n or ny < 0 or ny >= m :
                continue
            # 벽 부순 적이 없는 경우
            if z == 0 :
                # (nx, ny)에 방문한 적 없고 벽 없으면 그대로 이동
                if visited[0][nx][ny] == 0 and graph[nx][ny] == '0' :
                    visited[0][nx][ny] = visited[0][x][y] + 1
                    to_visit.append((nx, ny, 0))
                # (nx, ny)에 방문한 적 없고 벽 있으면 부수고 이동
                elif visited[1][nx][ny] == 0 and graph[nx][ny] == '1' :
                    visited[1][nx][ny] = visited[0][x][y] + 1
                    to_visit.append((nx, ny, 1))
            # 벽 부순 적 있는 경우
            else :
                # (nx, ny)에 방문한 적 없고 벽이 없으면 그대로 이동
                if visited[1][nx][ny] == 0 and graph[nx][ny] == '0' :
                    visited[1][nx][ny] = visited[1][x][y] + 1
                    to_visit.append((nx, ny, 1))
    return -1

print(bfs(0, 0))

'벽을 1번만 부술 때의 최단경로'를 구현하는게 어려웠다.

맵과 크기가 같은 2차원 리스트를 중첩한 3차원 리스트 visited 를 생성한다.

visited[0][x][y] 에는 벽을 부수지 않고 (x, y)까지의 최단경로, (0이면 방문한 적 없음)

visited[1][x][y] 에는 벽을 1번 부쉈을  (x, y)까지의 최단경로를 저장한다.

또한 방문한 좌표를 저장하는 큐 to_visit 에는 해당 좌표까지 이동하면서 벽을 부순 적이 있는지 여부를 추가로 저장한다.

이후의 코드에 대한 설명은 주석 참고

 

댓글