[백준] 2206 벽 부수고 이동하기 (Python 파이썬)

문제 설명

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다.

단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다.

(1, 1)에서 시작하여 (N,M)까지 가는데 최단거리를 출력하면 된다.

---

풀이 과정

전형적인 BFS 의 경로찾기 문제에 벽을 부술 수 있다는 특징이 포함된 문제이다.

중간에 벽을 단 한번만 부술 수 있기 때문에 벽을 부쉈는지의 여부를 3차원 행렬로써 나타내면 된다.

벽 부수기 없이 나타낸다면 visit[x][y] 라고 표현할 수 있지만 z를 추가함으로써 0은 안부숨, 1은 부숨을 표현할 수 있다.

즉, visited[x][y][0]은 안부순 경로, visited[x][y][1]은 부순 경로.

 

중간에 벽을 부순 경로는 그 이후의 경로부터는 벽을 지나갈 수 없으므로 벽이 아닌곳들만 탐색하면 되고,

중간에 벽을 부수지 않은 경로는 그 이후의 경로에서 벽을 부술 수 있는 선택권이 주어진다.

 

벽을 부술 수 있는 기회는 단 1번이고, 부술 지 말지를 선택할 수 있기 때문에

앞에서 if graph[nx][ny] == 1 and c == 0 : 처리를 해버리면, 무조건 앞에 나타나는 벽만 부수게 되는 것이 아니냐고 생각할 수 있는데, 같은 for문 안에서 4방향으로 이동하는 상황이고 그 중 다른방향으로 이동하는 것이 자동으로 벽을 부수지 않는 방향이기 때문에 상관 없다.

 

자세한 코드는 다음과 같다. 

from collections import deque

n, m = map(int, input().split())
graph = []

# 3차원 행렬을 통해 벽의 파괴를 파악함. visited[x][y][0]은 벽 파괴 가능. [x][y][1]은 불가능.
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1

for i in range(n):
    graph.append(list(map(int, input())))

# 상하좌우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x, y, z):
    queue = deque()
    queue.append((x, y, z))

    while queue:
        a, b, c = queue.popleft()
        # 끝 점에 도달하면 이동 횟수를 출력
        if a == n - 1 and b == m - 1:
            return visited[a][b][c]
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 다음 이동할 곳이 벽이고, 벽파괴기회를 사용하지 않은 경우
            if graph[nx][ny] == 1 and c == 0 :
                visited[nx][ny][1] = visited[a][b][0] + 1
                queue.append((nx, ny, 1))
            # 다음 이동할 곳이 벽이 아니고, 아직 한 번도 방문하지 않은 곳이면
            elif graph[nx][ny] == 0 and visited[nx][ny][c] == 0:
                visited[nx][ny][c] = visited[a][b][c] + 1
                queue.append((nx, ny, c))
    return -1


print(bfs(0, 0, 0))

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !