백준 6593 파이썬 - 상범 빌딩 BFS 알고리즘

문제

 

 

위 문제는 탈출할 수 있는 최단 거리를 구하는 문제인데, 2차원 배열이 아닌 3차원 배열을 통해 BFS 탐색을 진행해야 한다.

여러 개의 테스트 케이스를 받아 최단 거리를 출력해야 하므로, 무한 루프와 break 조건을 적절하게 설정해줘야 한다.

코드

from collections import deque
import sys
input = sys.stdin.readline

# 남북서동 상하
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

while True:
  L, R, C = map(int, input().split())
  
  if L == 0 and R == 0 and C == 0:
    break

  start = None
  board = []
  visited = [[[False] * C for _ in range(R)] for _ in range(L)]

  for i in range(L):
    board.append([list(input().strip()) for _ in range(R)])
    input()

    for x in range(R):
      for y in range(C):
        if board[i][x][y] == 'S':
          start = (x, y, i)

  def bfs(start):
    x, y, z = start
    que = deque([(x, y, z, 0)])
    visited[z][x][y] = True

    while que:
      x, y, z, time = que.popleft()

      if board[z][x][y] == 'E':
        return time

      for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        if 0 <= nx < R and 0 <= ny < C and 0 <= nz < L:
          if board[nz][nx][ny] != '#' and not visited[nz][nx][ny]:
            visited[nz][nx][ny] = True
            que.append((nx, ny, nz, time + 1))
            
    return -1

  result = bfs(start)
  
  if (result == -1):
    print("Trapped!")
  else:
    print(f"Escaped in {result} minute(s).")

3차원 배열 설정

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

while True:
  L, R, C = map(int, input().split())
  
  if L == 0 and R == 0 and C == 0:
    break

  start = None
  board = []
  visited = [[[False] * C for _ in range(R)] for _ in range(L)]

  for i in range(L):
    board.append([list(input().strip()) for _ in range(R)])
    input()

    for x in range(R):
      for y in range(C):
        if board[i][x][y] == 'S':
          start = (x, y, i)

• start 변수에 ‘S’ 의 위치를 지정한다.
• visited 배열은 방문 처리를 담당하는 배열인데, 3차원 배열의 크기에 맞게 잘 설정해줘야 한다.
  • C가 가로 개수 / R이 세로 개수 / L이 층 개수이다.
• board에 각 층에 상황을 입력하고, 층이 바뀔 때마다 enter가 입력되는데 이를 input() 으로 처리하였다.
• 각 층에 데이터를 입력하면서 ‘S’ 시작 위치를 찾아준다.

def bfs(start):
    x, y, z = start
    que = deque([(x, y, z, 0)])
    visited[z][x][y] = True

    while que:
      x, y, z, time = que.popleft()

      if board[z][x][y] == 'E':
        return time

      for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        if 0 <= nx < R and 0 <= ny < C and 0 <= nz < L:
          if board[nz][nx][ny] != '#' and not visited[nz][nx][ny]:
            visited[nz][nx][ny] = True
            que.append((nx, ny, nz, time + 1))
            
    return -1

 

bfs 함수는 일반 bfs 알고리즘이랑 크게 다르지 않다.

2차원에서 3차원으로 변경되어 z 축까지만 신경써주면 된다.

배운점

3차원 배열 문제는 많이 안 풀어봤는데, 신경 써야 하는 축이 한 개 더 생겼을 뿐이지 크게 어렵지 않게 느껴졌다.
그리고 이동 가능한 칸인지 확인할 때 ≠ ‘.’ 으로 확인했었는데, 이렇게 하면 ‘E’도 찾을 수 없어 ‘#’이 아닌지 확인해야 올바르게 문제를 풀 수 있었다. 이동 가능한 칸인지 올바르게 문제를 읽어야겠다..