[ BOJ / 파이썬 ] 2206 벽 부수고 이동하기

/  제출 1  /  ( 소요 시간 : 30분 )

import sys

input = sys.stdin.readline
from collections import deque


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

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

board = []
walls = []
for i in range(n):
  line = list(map(int, input().strip()))
  for j in range(m):
    if line[j] == 1:
      walls.append((i, j))
  board.append(line)

result = []
for wall in walls:
  i, j = wall
  board[i][j] = 0
  q = deque([(0, 0)])
  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 board[nx][ny] == 0:
        board[nx][ny] = board[x][y] + 1
        q.append((nx, ny))

  if board[n-1][m-1] != 0:
    result.append(board[n-1][m-1]+1)
  else:
    result.append(-1)

print(min(result))

21퍼센트 채점하고 틀렸습니다가 뜬다. 일부 테케는 맞춘다는건데.. 어디서 오류가 있는걸까. 빠르게 찾아보겠다.

 

: 아 이건 왜인지 알겠네요. result에 -1을 넣고, 마지막에 min값으로 결과를 빼줬으니 사실 -1이 나올 확률도 있고,

: board자체를 수정해서 첫 계산 이후에는 다시 원래대로의 board값이 아닌 전혀 다른 모양을 가지고 계산을 하게 되는 모양새입니다.

: 따라서 visited를 매번 따로 두어 그것을 계산하게 했는데요.

 

/  제출 2  / ( 소요 시간 : 이전 제출 +15분 )

import sys

input = sys.stdin.readline
from collections import deque


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

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

board = []
walls = []
for i in range(n):
  line = list(map(int, input().strip()))
  for j in range(m):
    if line[j] == 1:
      walls.append((i, j))
  board.append(line)

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

  
  if visited[n-1][m-1] != 0:
    result.append(visited[n-1][m-1])

  board[a][b] = 1

if result:
  print(min(result))
else:
  print(-1)

이건 또 시간초과가 납니다. ㅎ

그럴만도 한게 visited를 최악 1000*1000하는 계산을 벽의 개수만큼 하니, 벽이 1000개 가깝다면 1000^3번 연산하게 됩니다. 여기에 본연산을 또 더한다면 정말 성능이 떨어집니다. 

 

https://hongcoding.tistory.com/18

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

 

https://seongonion.tistory.com/m/107

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

어우 친절한 설명 굿..

 

/  제출 2  /

import sys

input = sys.stdin.readline
from collections import deque


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

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

board = []
for i in range(n):
  line = list(map(int, input().strip()))
  board.append(line)

def bfs():
  visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
  visited[0][0][0] = 1
  q = deque([(0, 0, 0)])
  
  while q:
    x, y, w = q.popleft()

    if x == n - 1 and y == m - 1:
      return visited[x][y][w]
      
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < m:
        # 현재 위치로 이동 가능하고, 아직 방문도 안 했다면
        if board[nx][ny] == 0 and visited[nx][ny][w] == 0:
          visited[nx][ny][w] = visited[x][y][w] + 1
          q.append([nx, ny, w])

        # 현재 위치가 벽이고, 아직 지금까지 부수지 않았다면(nx,ny이전에 x,y의 상태가 0인 경우)
        if board[nx][ny] == 1 and w == 0:
          visited[nx][ny][w+1] = visited[x][y][w] + 1
          q.append([nx, ny, w+1])

  # q돌면서 목표지점 나와서 리턴하는게 불가능한 상태니까 -1리텅ㄴ
  return -1

print(bfs())

: 이러면 배열을 하나 더 썼을 뿐이지 기존 BFS코드에서 시간복잡도를 한 사이클 더 돌리게 되지 않는다. 그래서 시간 내로 연산이 가능해진 것.