[백준] 2206번(python 파이썬)

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

 

---

미로와 같은 방식으로 풀 수 있지만 벽을 최대 한번 부실 수 있다는 조건이 있다.

처음 생각한 방법은 다음 좌표에 대해서 벽이 있을경우 그 벽을 깨고 그 자리에서 다시 BFS를 수행하는 것이었다.

즉 BFS( BFS ) 이렇게 중첩이 되는데 제출 결과 시간 초과 에러가 나왔다.

시간 복잡도를 보게되면 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색하니까 O(NM)^2)가 된다.

배열의 가로와 세로의 입력이 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000) 이렇게 제한이 되어있는데 N과 M이 1000일경우 NM은 1,000,000이 되고 NM^2은 1,000,000,000,000가 되니.. 시간초과가 뜨는게 당연하다.

3시간이나 붙잡고 풀었는데 참...

 

정답 풀이는 3차원 배열을 사용하여 벽을 부수고 가는 경우(1)와 부수고 가지 않는 경우(0)로 상태를 나눠서 푸는 것이다.큐에 방문 좌표와 상태( 0 or 1 )를 같이 넣는다. 

 

예시

- 큐에서 꺼낸 좌표의 상, 하, 좌, 우가 0인 경우와 visited[][][state] == 0일때 벽을 부수지 않고 이동한다.

  즉, 다음 좌표와 현재 상태를 큐에 넣고, 다음 방문할 좌표(이전에 부수고 온경우 visited[][][1]을 수정, 부수고 오지 않았

  을경우 visited[][][1]의 값을 수정할 것이다. )에 현재 좌표의 해당값 + 1 을 해준다. 

 

- 상, 하, 좌, 우가 1이고 이전에 벽을 부수지 않은 상태(0)라면 벽을 부수고 이동한다.

  즉, 이전에 벽을 부수지 않은 상태니 현재상태는 0 이다. 벽을 부셔야 하기때문에 다음 좌표와 현재 상태 + 1을 넣어주

  고, 벽을 부셨기때문에 visited[][][1]의 값을 수정해 준다.

 

말로 풀어서 설명하려고 하니까 어려운 것같다...

상태를 저장해야 한다는 것이 중요하다.

---

from collections import deque

row, col = map(int, input().split())
graph = [list(map(int, input())) for _ in range(row)]
visited = [[[0] * 2 for _ in range(col)] for _ in range(row)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def Bfs(start_x, start_y, iscrash, visited, graph):
    #crash 0: 벽안부시고 가는경우, 1: 부신 경우
    queue = deque()
    queue.append((start_x, start_y, iscrash))
    visited[start_x][start_y][iscrash] = 1

    while queue:
        cur_x, cur_y, iscrash = queue.popleft()
        if cur_x == row - 1 and cur_y == col - 1:
            return visited[cur_x][cur_y][iscrash]
        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
                continue
            # 벽 안부수고 이동
            if graph[next_x][next_y] == 0 and visited[next_x][next_y][iscrash] == 0:
                queue.append((next_x, next_y, iscrash))
                visited[next_x][next_y][iscrash] = visited[cur_x][cur_y][iscrash] + 1
            # 벽 부수고 이동
            if graph[next_x][next_y] == 1 and iscrash == 0:
                queue.append((next_x, next_y, iscrash + 1))
                visited[next_x][next_y][iscrash + 1] = visited[cur_x][cur_y][iscrash] + 1

    return -1

print(Bfs(0, 0, 0, visited, graph))