[BOJ] 2206. 벽 부수고 이동하기

Jimeaning·2023년 7월 2일

BFS 그래프

코딩테스트

목록 보기

105/143

Python3

문제

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

키워드

그래프 탐색
너비 우선 탐색

문제 풀이

문제 요구사항

N×M의 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
(1, 1)에서 (N, M)의 위치까지 최단 경로로 이동하려 한다. (시작하는 칸과 끝나는 칸도 포함해서 센다.)
-> 최단 경로 문제 BFS로 풀어야 함
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
-> 이 문제가 가진 포인트

변수 및 함수 설명

n, m: 맵 크기 (1 ≤ N, M ≤ 1,000)
dy, dx: 상하좌우 이동
adjMatrix: 맵 정보가 저장된 2차원 리스트
visited: 방문 처리 리스트 (3차원)
queue: bfs 탐색에 사용되는 큐
curY, curX, curZ: 현재 위치와 벽을 부쉈는지 확인하는 변수
ny, nx: 다음에 이동할 위치

bfs(): bfs를 구현하는 함수

풀이

(입력 및 선언)

맵 크기를 입력 받는다
맵 정보를 2차원 리스트 형태로 저장한다

(bfs 함수)

큐에 원소가 남아 있지 않을 때까지 반복한다
큐의 첫 번째 원소를 꺼내 curY, curX, curZ 변수에 저장한다.
만약 현재 위치가 n-1, m-1이라면, 목적지까지 도달했기 때문에 visited[curY][curX][curZ] 값을 반환한다

총 4번 (상하좌우) 반복한다
다음으로 이동할 위치가 맵 바깥이라면 건너뛴다.
다음 이동할 위치가 벽인데, 아직 한 번도 벽을 깬 적이 없다면 벽을 부술 수 있다.
(visited[x][y][0]은 안 부순 경로, visited[x][y][1]은 부순 경로라고 표시)
부순 경로를 표시하고, 큐에 ny, nx, 1을 넣는다.
벽을 부순 이후에는 벽을 지나갈 수 없으므로, 벽이 아닌 곳만 탐색하면 된다.
만약 다음 이동할 곳이 벽이 아니고, 아직 한 번도 방문하지 않은 곳이라면
방문 처리를 한 후 큐에 ny, nz, curZ를 넣는다.

큐를 다 돌고도 목적지에 도달하지 못하면 -1을 리턴한다.

(맵 시작)

0, 0부터 탐색하게 되고, 벽을 부순 상태도 0으로 큐에 넣는다.
visited[0][0][0]에 방문처리로 1을 넣어준다. (시작하는 칸과 끝나는 칸 모두 센다고 하였으므로)
bfs 함수를 실행하고 리턴 값을 출력한다.

최종 코드

from collections import deque

n, m = map(int, input().split())

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

adjMatrix = []
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
queue = deque([])

for _ in range(n):
    adjMatrix.append(list(map(int, input())))

def bfs():
    while queue:
        curY, curX, curZ = queue.popleft()
        if curY == n-1 and curX == m-1:
            return visited[curY][curX][curZ]
        for i in range(4):
            ny = curY + dy[i]
            nx = curX + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            if adjMatrix[ny][nx] == 1 and curZ == 0:
                visited[ny][nx][1] = visited[curY][curX][0] + 1
                queue.append((ny, nx, 1))
            if adjMatrix[ny][nx] == 0 and visited[ny][nx][curZ] == 0:
                visited[ny][nx][curZ] = visited[curY][curX][curZ] + 1
                queue.append((ny, nx, curZ))
    return -1

visited[0][0][0] = 1
queue.append((0, 0, 0))
print(bfs())