[파이썬] 백준 6593 : 상범 빌딩 (골드5)

[파이썬] 백준 6593 : 상범 빌딩 (골드5)

 

6593번: 상범 빌딩

 

---

문제

---

풀이

0. 방향성 생각

최단거리 문제. BFS를 사용한다

1. BFS 함수 정의

import sys
input = sys.stdin.readline
from collections import deque
step = [[1,-1,0,0,0,0],[0,0,1,-1,0,0],[0,0,0,0,1,-1]]

def bfs(x,y,z):
    q = deque()
    q.append((x,y,z))
    arr[z][y][x] = 0
    
    while q:       
        x,y,z = q.popleft()
        visit[z][y][x] = True
        
        for i in range(6):
            nx = x + step[0][i]
            ny = y + step[1][i]
            nz = z + step[2][i]
            
            if 0<=nx<w and 0<=ny<h and 0<=nz<d :
                if arr[nz][ny][nx]!='#' and not visit[nz][ny][nx] :
                    visit[nz][ny][nx] = True
                    
                    if arr[nz][ny][nx] == 'E' : 
                        arr[nz][ny][nx] = arr[z][y][x] + 1 
                        return arr[nz][ny][nx]
                    else : 
                        arr[nz][ny][nx] = arr[z][y][x] + 1
                        q.append((nx,ny,nz))

6방향 탐색할 방향을 정해준다.

큐에 시작할 위치인 x,y,x를 넣고 시작한다. 시작점은 0부터 시작한다.

6방향을 탐색했을 때 벽이 아니고 탐색을 안했다면 visit을 True로 바꿔준다.

탈출지점을 만났으면 이전 값에 +1을 해주고 리턴값을 얻는다. 아닌 경우 이전 값에 +1을 해주고 큐에 추가한다.

2. 출력

while True :
    d,h,w = map(int,input().split())
    
    if d==0 and w==0 and h==0 :
        break
        
    else :
        arr = [] 
        for i in range(d): 
            temp = [] 
            for j in range(h):
                s = list(input().rstrip())
                temp.append(s)
                if 'S' in s :
                    a,b,c = (s.index('S'),j,i)
            arr.append(temp) 
            temp = input()
            
    visit = [[[False]*w for i in range(h)] for j in range(d)]
    answer = bfs(a,b,c) 
    if answer == None:
        print('Trapped!')
    else :
        print(f'Escaped in {answer} minute(s).')

층수 d, 세로 h, 가로 d를 받아준다.

모두 0일 경우 탈출한다. 아닌 경우 어레이를 만들어준다. 이 때 시작지점 S의 위치를 찾아서 변수에 할당한다.

방문 체크할 리스트 visit을 만들고 bfs를 진행한다.

만약 탐색 후 리턴값을 얻지 못했다면 answer은 None이고 이 때 Trapped!을 출력한다,.

아닌 경우 탈출 지점까지 거리를 출력한다.

---

전체 코드

import sys
input = sys.stdin.readline
from collections import deque
step = [[1,-1,0,0,0,0],[0,0,1,-1,0,0],[0,0,0,0,1,-1]]

def bfs(x,y,z):
    q = deque()
    q.append((x,y,z))
    arr[z][y][x] = 0
    
    while q:       
        x,y,z = q.popleft()
        visit[z][y][x] = True
        
        for i in range(6):
            nx = x + step[0][i]
            ny = y + step[1][i]
            nz = z + step[2][i]
            
            if 0<=nx<w and 0<=ny<h and 0<=nz<d :
                if arr[nz][ny][nx]!='#' and not visit[nz][ny][nx] :
                    visit[nz][ny][nx] = True
                    if arr[nz][ny][nx] == 'E' : 
                        arr[nz][ny][nx] = arr[z][y][x] + 1 
                        return arr[nz][ny][nx]
                    else : 
                        arr[nz][ny][nx] = arr[z][y][x] + 1
                        q.append((nx,ny,nz))
                        
while True :
    d,h,w = map(int,input().split())
    
    if d==0 and w==0 and h==0 :
        break
        
    else :
        arr = [] 
        for i in range(d): 
            temp = [] 
            for j in range(h):
                s = list(input().rstrip())
                temp.append(s)
                if 'S' in s :
                    a,b,c = (s.index('S'),j,i)
            arr.append(temp) 
            temp = input()
            
    visit = [[[False]*w for i in range(h)] for j in range(d)]
    answer = bfs(a,b,c) 
    if answer == None:
        print('Trapped!')
    else :
        print(f'Escaped in {answer} minute(s).')

그냥 무난한 BFS 문제.