[Python] 백준 2206, 백준 14442 (벽 부수고 이동하기 1, 2)

1. 문제: https://www.acmicpc.net/problem/2206

최단 경로를 구하는 BFS이되 벽을 부순 여부를 매번 같이 탐색해야하므로,

visited는 x, y, 벽 부순 여부의 상태를 가진 3차원 배열로 설계하고, 큐는 x, y, 벽 부순 여부의 상태를 가진 것으로 설계한다.

 

✅ 풀이

from collections import deque

n, m = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
board = []
INF = int(1e9)
for _ in range(n):
  board.append(list(map(int, list(input()))))
visited = [[[INF] * 2 for _ in range(m)] for _ in range(n)]   
# 벽을 부쉈을때와 안부쉈을 때의 각각의 최단거리이므로, 원소 2개를 가지는 3차원 배열로 설계한다.
q = deque([])

q.append((0, 0, 0))     # 처음에 벽을 부수지 않는 상태에서 시작하므로 wall이 0인 상태에서 초기화 시작
visited[0][0][0]= 1

while q:
  x, y, wall = q.popleft()

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

    if not (0<=nx<n and 0<=ny<m and visited[nx][ny][wall] == INF):   # 이미 방문했거나 좌표 범위를 벗어났을 경우 pass
      continue

    if board[nx][ny] == 0:    # 원래 통과할 수 있는 길이므로 통상적으로 처리
      visited[nx][ny][wall] = visited[x][y][wall] + 1
      q.append((nx, ny, wall))
      # 이때에는 이전에 벽을 부쉈든 안부쉈든 상관 없으니까 큐에서 뽑은 wall 그대로를 큐에 처리하고 visited 처리하게 됨

    if board[nx][ny] == 1 and wall == 0:    # 통과할 수 없는 벽이지만 벽을 아직 부수지 않은 경우
      visited[nx][ny][1] = visited[x][y][wall] + 1     # 부순케이스로 방문 처리 및 큐에 추가
      q.append((nx, ny, 1))
    
print(min(visited[n-1][m-1]) if min(visited[n-1][m-1]) != INF else -1)

 

2. 문제: https://www.acmicpc.net/problem/14442

위 문제에서 변형된 문제로, 이제는 벽을 최대 k개 부술 수 있다.

 

❌ 시간초과 풀이 (하단 풀이는 24%에서 시간초과 나는 풀이이다.)

from collections import deque

n, m, k = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
board = []
INF = int(1e9)
for _ in range(n):
  board.append(list(map(int, list(input()))))
visited = [[[INF] * (k+1) for _ in range(m)] for _ in range(n)]    # 0부터 k개까지 가능하므로 인덱스를 위해 (k+1) 갯수만큼 초기화
q = deque([])

q.append((0, 0, 0))
visited[0][0][0] = 1

while q:
  x, y, wall = q.popleft()

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

    if not (0<=nx<n and 0<=ny<m and visited[nx][ny][wall] == INF):
      continue

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

    if board[nx][ny] == 1 and wall < k:   # <-- 여기가 문제
      visited[nx][ny][wall + 1] = visited[x][y][wall] + 1
      q.append((nx, ny, wall + 1))
    
print(min(visited[n-1][m-1]) if min(visited[n-1][m-1]) != INF else -1)

 

여기서 시간초과의 원인이 되는 부분은 다음과 같다.

 

    if board[nx][ny] == 1 and wall < k:   # <-- 여기가 문제
      visited[nx][ny][wall + 1] = visited[x][y][wall] + 1
      q.append((nx, ny, wall + 1))

 

현재의 부순 벽의 갯수가 k개 미만이라면 벽을 하나 더 부수면서 갈 수 있다는 의미이므로, 벽을 하나 더 부수었을 때의 방문 여부를 확인해야하나 해당 방문 여부를 체크하지 않은 채 계속 visited 처리하므로,

한번 방문한 visited[x][y][wall + 1]을 계속 반복하고 큐에 추가하게 되어 이미 방문하여 계산한 값을 불필요하게 연산하게 된다.

 

따라서 다음과같이 코드를 수정하면 통과한다.

 

✅ 풀이

from collections import deque

n, m, k = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
board = []
INF = int(1e9)
for _ in range(n):
  board.append(list(map(int, list(input()))))
visited = [[[INF] * (k+1) for _ in range(m)] for _ in range(n)]    # 0부터 k개까지 가능하므로 인덱스를 위해 (k+1) 갯수만큼 초기화
q = deque([])

q.append((0, 0, 0))
visited[0][0][0] = 1

while q:
  x, y, wall = q.popleft()

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

    if not (0<=nx<n and 0<=ny<m):    # <-- 수정한 부분
      continue

    if board[nx][ny] == 0 and visited[nx][ny][wall] == INF:  # 벽을 안부수는 경우  <-- 수정한 부분
      visited[nx][ny][wall] = visited[x][y][wall] + 1
      q.append((nx, ny, wall))

    if board[nx][ny] == 1 and wall < k and visited[nx][ny][wall + 1] == INF:  # 벽을 부수는 경우   <-- 수정한 부분
      visited[nx][ny][wall + 1] = visited[x][y][wall] + 1
      q.append((nx, ny, wall + 1))
    
print(min(visited[n-1][m-1]) if min(visited[n-1][m-1]) != INF else -1)