[백준 2206번] 벽 부수고 이동하기 - 파이썬

문제 링크:

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

2206번: 벽 부수고 이동하기

 

---

풀이 유형:

그래프 이론, 그래프 탐색, 너비 우선 탐색, 시물레이션

 

★문제풀이 Point★

1. 벽을 부술 수 있는 경우는 단 1번!

2. 2차원 리스트가 아닌 3차원 리스트로 풀어야 한다.

 

풀이 과정:

이 문제는 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하는 문제이다.

단, 벽을 부술 수 있는 개수가 최대 1개임이 핵심이다.

필자는 다음 포스트에 있는 bfs 문제 푸는 방식처럼 2차원 리스트를 만들어 접근하려고 했다.

https://data-flower.tistory.com/84

[백준 16234번] 인구 이동 - 파이썬

 

예제 결과는 다 맞았지만 결과 5%에서 출력 오류가 뜬 모습을 확인하였다.

2차원 배열로 실패한 원인을 살펴보니 2가지가 있었다. 

1. 시간 복잡도

이 문제는 N, M이 최대 1000을 입력받을 수 있으므로 O(NM)은 1,000,000번 반복한다.

2차원 리스트로 풀게 되면, 각 위치마다 벽을 부술 수 있는지 없는지를 확인해야 하기 때문에 시간 복잡도가 O(NM^2)인 1,000,000,000,000(1조)가 되므로 시간 초과가 당연히 뜬다.

2. 반례

0	0	0	0
0	1	0	0
1	1	1	1
0	0	0	0

 

이 맵은 'ㄱ' 방향으로 최단 거리를 구할 수 있는 맵이다.

파란색으로 표시된 곳은 굳이 벽을 뚫지 않고 올 수 있다.

하지만 연두색 1로 표시된 곳을 벽으로 뚫고 지나오게 된다면, 밑에 있는 벽을 뚫을 수가 없다.

정리하면, 벽을 부수고 온 경우가 벽을 부수고 오지 않는 경우보다 먼저 방문하게 된다면, 이를 불가능으로 판단하여 -1을 출력한다.

 

이 두 가지 원인으로 인해 3차원 배열을 만들어야 한다.

벽을 부수고 오는 경우(wall_break_left = 0)와 벽을 부수지 않고 오는 경우(wall_break_left = 1)를 각각 실행하여 문제를 해결한다.

 

백준 2206번 채점결과

 

풀이 코드:

# 2206번 벽 부수고 이동하기

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
# 3차원 리스트(행, 열, 벽을 깬 여부) 생성
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
# 상하좌우 이동 표시
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 큐가 빌 때까지 반복
def solve(x, y, wall_break_left, visited, graph):
    q = deque()
    # 큐에 시작 위치 삽입
    q.append((x, y, wall_break_left))
    # 방문 표시
    visited[x][y][wall_break_left] = 1
    # 큐가 빌 때까지 반복
    while q:
        x, y, wall_break_left = q.popleft()
        # 도착할 위치에 도착하였다면
        if x == n -1 and y == m -1:
            # 최단거리 횟수 리턴
            return visited[x][y][wall_break_left]
        # 이동할 수 있는 4가지 방향에 대하여
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵을 벗어나면 건너뛰기
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽을 부수지 않고 이동
            if graph[nx][ny] == 0 and visited[nx][ny][wall_break_left] == 0:
                q.append((nx, ny, wall_break_left))
                visited[nx][ny][wall_break_left] = visited[x][y][wall_break_left] + 1
            # 벽을 부수고 이동
            if graph[nx][ny] == 1 and wall_break_left == 1:
                q.append((nx, ny, wall_break_left - 1))
                visited[nx][ny][wall_break_left - 1] = visited[x][y][wall_break_left] + 1
    # 불가능할 경우 -1 리턴
    return -1

# 결과 출력
print(solve(0, 0, 1, visited, graph))

 

 

 

2206번 벽 부수고 이동하기