[백준6593&파이썬] BFS로 3차원 공간을 탐색할 수 있다.

# 문제

백준 6593 상범빌딩 파이썬 풀이

6593번: 상범 빌딩

# 코드

import sys
from collections import deque

dirs = [
  (-1, 0, 0),  # 아래
  (0, -1, 0), (0, 0, 1), (0, 1, 0), (0, 0, -1),  # 상하좌우
  (1, 0, 0)  # 위로
  ]


def solve(L, R, C):
  board = list()
  start_point = [-1, -1, -1]
  flag = True

  ### BOARD 구성 ###
  for l in range(L):
    temp = list()
    for r in range(R + 1):
      inputStr = str(sys.stdin.readline().strip())
      line = list(inputStr)
      if len(line) == 0:
        continue
      if flag and 'S' in inputStr:
        c = inputStr.find('S')
        if c != -1:
          start_point[0] = l
          start_point[1] = r
          start_point[2] = c
          flag = False

      temp.append(line)
    board.append(temp)

  # print(board)
  # print("start_point : ", start_point)
  #####################

  dq = deque()
  dq.append((start_point[0], start_point[1], start_point[2], 0))  # 초기 시작값
  board[start_point[0]][start_point[1]][start_point[2]] = "#"  # # 방문 처리

  while len(dq) != 0:
    cur = dq.popleft()  # 꺼내기

    for dir in dirs:
      next = (cur[0] + dir[0], cur[1] + dir[1], cur[2] + dir[2], cur[3] + 1)

      if 0 <= next[0] < L and 0 <= next[1] < R and 0 <= next[2] < C:  # 범위 안인지 확인
        if board[next[0]][next[1]][next[2]] == ".":  # 갈 수 있는 곳인지 확인
          dq.append(next)  # 추가해주기
          board[next[0]][next[1]][next[2]] = "#"  # 방문처리

        elif board[next[0]][next[1]][next[2]] == "E":  # 목표 지점이면
          return next[3]  # 끝내기
  return -1


while True:
  L, R, C = map(int, sys.stdin.readline().split())
  # L 층 수
  # R 행, C 열
  if L == 0 and R == 0 and C == 0:
    break
  result = solve(L, R, C)
  if result == -1:
    print("Trapped!")
  else:
    print(f"Escaped in {result} minute(s).")

 

# 풀이

## BFS로 3차원 공간을 탐색할 수 있다.

dirs = [
  (-1, 0, 0),  # 아래
  (0, -1, 0), (0, 0, 1), (0, 1, 0), (0, 0, -1),  # 상하좌우
  (1, 0, 0)  # 위로
  ]

• 3차원은 그냥 하나의 차원만 추가시키면 된다 별로 어렵지 않다.  대신 범위도 한차원 추가해서 검사해야 한다.

if 0 <= next[0] < L and 0 <= next[1] < R and 0 <= next[2] < C:  # 범위 안인지 확인

 

## 시작 지점을 기록한다면 꽤 유용하게 사용된다.

• 문제에서 시작위치가 "S"가 되게 된다. 이 "S" 를 문자를 입력받을때 미리 저장해둔다면, 추후에 모든 3차원 공간을 for문을 돌면서 S를 찾을 필요가 없다. 

  if flag and 'S' in inputStr:
    c = inputStr.find('S')

 

## 문자열을 이용하지말고, 한 문자씩 배열에 담아야지 수정이 가능하다.

• 문자열(STRING)을 리스트에 한글자씩 쪼개서 담으려면 .split()을 이용하는 것이 아니다. 문자열을 list()로 만들면 된다.
• 백준 문제를 풀때는 아래와 같이 이용하자

inputStr = str(sys.stdin.readline().strip())
line = list(inputStr)

 

## find 메소드를 사용하자

• find는 문자열에서 문자열을 찾아준다. 찾는다면 해당 인덱스를 찾지 못한다면 -1을 리턴한다.

c = inputStr.find('S')
if c != -1:
  start_point[0] = l
  start_point[1] = r
  start_point[2] = c

 

## 찾을 문자 in 문자열 이다.

if 'S' in inputStr:

이건 맨날 헷갈린다. "S"가 문자열 안에 있냐? 로 생각하자

 

## l[0] == 'S' 와 l[0] =="S"는 똑같으니까 시간날리지 말자

l = ['S',"S",'E',"E"]
print(l)

if l[0] == 'S' : # or l[0] == "S"
  print(True)
else :
  print(False)

• 해보니까 똑같다. 이걸로 시간 날리지 말자