백준 2206 - 파이썬

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

2206번: 벽 부수고 이동하기

문제 풀이

이 문제에서 핵심은 벽을 어떻게 부시고 탐색하냐는 것이다. 처음에는 백트래킹을 써서 풀려고 했다. 아직 시간 복잡도에 대한 개념이 익숙하지 않지만 계산해보면 다음과 같다. 

 

1. 이중 반복문에서 모든 경우를 체크할 때의 시간복잡도: O(N x M)

2. bfs를 실행할 때의 시간복잡도: O(v + e) = O(N x M + 4 x N x M) = O(N x M)

 

따라서 시간복잡도는 O(N^2 x M^2)가 된다.

 

n과 m의 최대 개수는 1000이므로 1000 ^2 x 1000^2 = 1000000000000, 1조가 된다.

구글링을 통해 찾아보니 1억번이 1초에 계산된다 하니 총 10000초가 걸리는 셈이다.

 

결국, 백트래킹으로는 풀 수 없는 문제이기 때문에 다른 방법으로 풀어야 했다. 구글링을 해보니 다른 사람들은 3차원 배열을 통해 풀었다.

 

# 0: 이동할 수 있는 곳, 1: 이동할수 없는 벽
#(1,1)에서 (n,m)의 위치까지 최단경로로 이동하려 함.
# 벽 하나까지는 뿌시고 이동해도 됨

import sys
from collections import deque

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

graph = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

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

ans = 0

def bfs():
  q = deque([(0, 0, 0)])
  visited[0][0][0] = 1

  while q:
    x, y, wall = q.popleft()
    if x == n - 1 and y == m -1:
      return visited[x][y][wall]

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

      if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][wall] == 0:
        if graph[nx][ny] == 0:
          q.append((nx, ny, wall))
          visited[nx][ny][wall] = visited[x][y][wall] + 1

        if wall == 0 and graph[nx][ny] == 1:
          q.append((nx, ny, 1))
          visited[nx][ny][1] = visited[x][y][wall] + 1

  return -1

print(bfs())

 

시간복잡도 계산하는 방법을 추상적으로만 이해하고 있어 문제를 풀때 적용한 적이 없었는데, 이번 문제를 풀면서 어떻게 계산해봐야 할지 구체적으로 알게 되었다. 또한 3원배열을 쓰면 시간초과가 날거라 생각하고 있었는데 막상 해보니 오히려 더 시간이 단축되었다. 아직 모든 문제의 시간 복잡도를 한번에 계산하기는 힘들지만 문제를 풀면서 시간복잡도 계산하는 연습도 해봐야 되겠다.