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

문제 링크

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

2206번: 벽 부수고 이동하기

 

풀이 

- 뚫을 수 있는 경우의 수마다 계산해서 풀려고 했는데 시간초과 

# 시간 초과 
from collections import deque 
from itertools import combinations 

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

def bfs(a,b,n,m):
    visited = [[0] * m for _ in range(n) ]
    visited[a][b] = 1
    
    q = deque()
    q.append((a,b))
    
    while q:
        x,y = q.popleft()
        
        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] == 0 and graph[nx][ny]== 0:
                visited[nx][ny] = visited[x][y] + 1 
                q.append((nx,ny))
                

    return visited[n-1][m-1]

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

graph = []

for _ in range(n):
    graph.append(list(map(int,input())))
    
wall = []
# 벽의 위치 인덱스 
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 :
            wall.append([i,j])
# 벽 안뚫었을 때 결과 
result = bfs(0,0,n,m)
if result == 0 :
    result = int(1e9)

# 벽 하나씩 뚫었을 때 
for i in wall :
    graph[i[0]][i[1]] = 0
    
    tmp = bfs(0,0,n,m)
    if tmp != 0 :
        result = min(result, tmp)
    graph[i[0]][i[1]] = 1

if result == int(1e9):
    print(-1)
else:
    print(result)

- bfs의 3차원 배열을 이용하여 푸는 문제 

- visited에 거리를 기록하는데, 벽을 뚫었을 때와 안 뚫었을 때를 나누어서 기록

 visited[x][y][1]은 벽을 뚫을 수 있는 상태 

 visited[x][y][0]은 벽을 한번 뚫은 상태 

from collections import deque 

nx = [ 1, -1, 0, 0 ]
ny = [ 0, 0, 1, -1 ]

def bfs():
  
  # 3차원 배열 
  visited = [ [[0] * 2 for _ in range(m)] for _ in range(n)]

  # 벽을 뚫을 수 있는 상태에서 시작, 방문 표시 
  visited[0][0][1] = 1 
   
  q = deque()
  # 벽을 뚫을 수 있는 상태 
  q.append((0,0,1))

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

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

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

      if 0<= dx < n and 0<= dy < m:
        # 벽이 아니고 방문한 적이 없다면 
        if maps[dx][dy] == 0 and visited[dx][dy][w] == 0:
          # 거리 기록 
          visited[dx][dy][w] = visited[x][y][w] + 1 
          q.append((dx,dy,w))
        # 벽이고 뚫을 수 있는 상태라면 
        elif maps[dx][dy] == 1 and w == 1 :
          visited[dx][dy][0] = visited[x][y][1] + 1 
          q.append((dx, dy, 0))

  return -1

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

maps = []

for _ in range(n):
  maps.append(list(map(int,input())))

print(bfs())