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

문제

2206번: 벽 부수고 이동하기

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 시간복잡도를 생각해보면 단순 bfs 탐색을 통해 문제를 풀면 시간초과가 나오는 것을 확인할 수 있다.

- 방문 여부에 따른 탐색이 아닌 벽을 부실 수 있는 상태, 벽을 못 부시는 상태 이 2가지 상태에 따라서 탐색을 해야한다.

- 벽을 만났고 부실 수 있는 상태라면 벽을 부순 후 상태를 바꿔주어 이동횟수를 초기화한 후 큐에 담는다.

- 벽이 아닌 이동 가능한 곳이고 현재 상태로 처음 이동한 곳이라면 이동횟수를 초기화한 후 큐에 담는다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs():
    queue = deque([[0, 0, 0]])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[0][0][0] = 1 # 첫 번째칸에 벽을 부실 수 있는 상태에 칸의 이동 횟수

    while queue:
        x, y, z = queue.popleft()

        # (n, m)의 위치까지 이동했다면 리턴
        if x == n - 1 and y == m - 1:
            return visited[x][y][z]

        # 상/하/좌/우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내에 있으면
            if 0 <= nx < n and 0 <= ny < m:
                # 벽을 만나고 벽을 부실 수 있는 상태라면
                if graph[nx][ny] == 1 and z == 0:
                    visited[nx][ny][z + 1] = visited[x][y][z] + 1
                    queue.append([nx, ny, z + 1])

                # 이동할 수 있는 곳이고 현재 상태로 처음 이동 하는 곳이라면
                elif graph[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append([nx, ny, z])

    # (n, m)의 위치까지 이동을 못했다면 -1 리턴
    return -1


n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().strip())) for i in range(n)]
# 3차원 배열
# x == 행
# y == 열
# z == 벽을 부실 수 있는지에 대한 상태(부실 수 있다 : 0, 부실 수 없다: 1)
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

print(bfs())

 

실패한 코드(11%.. 틀렸습니다.)

import sys
from collections import deque


def bfs():
    queue = deque([[0, 0, 0]])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[0][0] = 1

    while queue:
        x, y, z = queue.popleft()

        if x == n - 1 and y == m - 1:
            return visited[x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:

                if graph[nx][ny] == 0:
                    queue.append([nx, ny, z])
                    visited[nx][ny] = visited[x][y] + 1

                elif graph[nx][ny] == 1 and z == 0:
                    queue.append([nx, ny, z + 1])
                    visited[nx][ny] = visited[x][y] + 1

       return -1


n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().strip())) for i in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
print(bfs())

위 코드는 벽을 부실 수 있는 상태로 칸을 인동한건지 벽을 부실 수 없는 상태로 칸을 이동한건지 확인할 수 없고 그렇기에 틀렸다고 나온 것으로 판단된다. 이후 코드를 수정 후 여러 반례를 해결했지만 시간 초과가 나왔다.

이후에 heapq와 set()을 통해 시간초과를 해결하려 했지만, 마찬가지로 시간초과가 나오는 것을 확인할 수 있었다. 그래서 시간복잡도에 대해서 다시 생각을 하다보니 시간복잡도가 O(NM)^2인 것을 확인했고고 3차원 배열을 통해 벽을 부실 수 있는 상태와 부실 수 없는 상태로 나뉘어 시간 복잡도를 O(NM)을 통해 문제를 풀어야겠다고 생각했다.

위 문제를 풀면서 문제를 처음 풀 때 되도록이면 시간복잡도를 계산한 후 풀어야겠다는 생각을 했다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법