[Python/백준] 6593 상범 빌딩

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

6593번: 상범 빌딩

<문제 해설>

너비 우선 탐색 문제이다. 값을 받을때 중간에 빈칸이 들어간다는걸 계산안해서 index에러가 계속 나왔다 조심

이것만 조심하면 문제는 매우 간단하다.

빌딩의 공간의 정보를 표시할 3차원 배열을 만들어서 관리한다.

6가지 방향으로 움직일 수 있도록

move = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,-1],[0,0,1]]

 

배열을 만든다

bfs를 몇번 실행했는지 기록할 minutes를 만들어준다. 실행될때마다 minutes 에 1을 추가한다.

1. 문제의 주어진 값들을 다 받는다. S위치를 S배열에 [[z,y,x]]로 넣어준다.
2. bfs함수를 실행한다. S배열을 인자로 받아준다.
3. 다음 bfs에 사용할 새로운 S배열(newS)를 만들어준다. 
4. S 위치들을 저장한 배열을 읽는다. 빌딩에 현제 S를 상하좌우아래위로 움직여 주면서 '.'가 있는곳으로만 움직일수 있으니 '.'가 있으면 [mz,my,mx]를 newS배열에 넣어주고 bilding[mz][my][mx] =='S'로 바꿔서 이동한 곳이라는걸 기록해준다. 만약 이동한 곳이 E라면 탈출한거니 출력해준다.
5. 만약 newS에 아무것도 없다면 즉 이동할 곳이 없었다면 IMPOSSIBLE을 출력한다.
   있으면 1번으로 돌아간다.

<예시>

예시의 bilding를 minutes를 통해 보여주겠다.

minutes = 0

처음에 받은 값을 나타낸 모습이다.

minutes = 1

하, 우로 S가 1칸식 이동하며 이동했다는 걸 표시하는 모습이다.

minutes = 8

다음은 8에서 9으로 넘어갈때 1층에서 2층으로 S가 넘어가는 걸 보여준다.

minutes = 9

 

<코드>

def bfs(S):
    global minutes
    minutes += 1
    newS = []
    for s in S:
        for m in move:
            mz = m[0] + s[0]
            my = m[1] + s[1]
            mx = m[2] + s[2]
            if L > mz > -1 and R > my > -1 and C > mx > -1:
                if bilding[mz][my][mx] == 'E':
                    print(f'Escaped in {minutes} minute(s).')
                    return
                if bilding[mz][my][mx] == '.':
                    bilding[mz][my][mx] = 'S'
                    newS.append([mz,my,mx])
    if len(newS) == 0:
        print('Trapped!')
    else:
        bfs(newS)

import sys
sys.setrecursionlimit(10**7)

while(1):
    L,R,C = map(int,sys.stdin.readline().split())
    if [L,R,C] == [0,0,0]:
        break
    bilding = []
    move = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,-1],[0,0,1]]
    for l in range(L):
        floor = []
        for r in range(R):
            line = list(sys.stdin.readline().rstrip())
            for c in range(C):
                if line[c] == 'S':
                    S = [[l,r,c]]
            floor.append(line)
        bilding.append(floor)
        sys.stdin.readline()
    minutes = 0
    bfs(S)

<코드 설명>

def bfs(S): //너비 탐색 코드
    global minutes //minutes를 저장하는 변수
    minutes += 1 //함수가 실행될 때마다 1씩 증가한다.
    newS = [] //다음 너비 탐색에 사용할 S배열
    for s in S: //S 배열에있는 S들의 위치를 1개씩 거내서
        for m in move: //6가지 방향으로 움직이며 움직인 위치를 기록
            mz = m[0] + s[0]
            my = m[1] + s[1]
            mx = m[2] + s[2]
            if L > mz > -1 and R > my > -1 and C > mx > -1: //배열을 초과하지 않았다면
               if bilding[mz][my][mx] == 'E': //E라면 탈출구니 탈출
                    print(f'Escaped in {minutes} minute(s).') //탈출했음을 알림
                    return //더이상 실행할 필요 없으니 중지
                if bilding[mz][my][mx] == '.': // '.'로만 움직일 수 있으니 
                    bilding[mz][my][mx] = 'S' //움직이고 S로 움직였다는 것으 기록
                    newS.append([mz,my,mx]) //새로운 위치라고 newS에 넣어준다.
    if len(newS) == 0: //새로운 S가 존재하지 않으면
        print('Trapped!') //못나간다고 출력
    else:
        bfs(newS) //새로운 S들로 재귀함수

import sys
sys.setrecursionlimit(10**7)

while(1): //계속 반복
    L,R,C = map(int,sys.stdin.readline().split())  //값 받아오기
    if [L,R,C] == [0,0,0]:
        break
    bilding = []
    move = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,-1],[0,0,1]] //3차원 배열을 돌아다닐 배열
    for l in range(L):
        floor = []
        for r in range(R):
            line = list(sys.stdin.readline().rstrip())
            for c in range(C):
                if line[c] == 'S': //S가 입력됐다면 좌표 기록후 2차원 배열로 넣어주
                    S = [[l,r,c]]
            floor.append(line)
        bilding.append(floor)
        sys.stdin.readline()
    minutes = 0
    bfs(S)