[BOJ] 6593. 상범 빌딩(Python) / BFS

 

6593번: 상범 빌딩

빌딩의 상태를 3차원 배열로 받아 시작 위치부터 도착 위치까지 최단 거리로 갈 수 있는 경우의 거리를 구함

# 1시간 15분 소요

• 사용 알고리즘 : BFS 최단 거리 구하기
• 나의 비루한 코딩실력으로 인해 Input 받는 데만 28분이 걸렸다.. 별것도 아닌 것을.. 혼자 이상하게 생각ㅠ
• 이후로는 주어진 맵대로 3차원 배열인 것만 다르고 일반적인 BFS 문제와 같이 풀면 된다.
• Input 받으며 시작 좌표를 저장한다.(sl, sr, sc - 몇 층, 몇 행, 몇 열 순으로 위치 저장)
• bfs 내에서 주어진 빌딩의 맵 크기와 같은 크기의 visited 3차원 배열을 만들고 시작 위치를 1로 표시한다.
• Queue에 시작 위치를 담는다.
• 큐에서 값을 하나씩 빼며 6방향 (상하좌우 + 윗층, 아랫층) 탐색
• 범위 밖으로 나가거나 이미 방문 처리 되어 있거나 벽이면 continue
• 그렇지 않다면 갈 수 있으므로 다음 위치에 현 위치 + 1한 거리 값을 표시하고 큐에 담는다.
• 이동할 곳이 도착지("E")라면 출력 형식에 맞게 현재 거리를 출력하고 즉시 리턴
• 모든 큐의 탐색이 끝나도록 목적지에 도착하지 못하면 "Trapped!" 출력 

 

파이썬 코드는 다음과 같다.

---

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

dl = (-1, 1, 0, 0, 0, 0)
dr = (0, 0, -1, 1, 0, 0)
dc = (0, 0, 0, 0, -1, 1)

def bfs():
    visited = [[[0] * C for _ in range(R)] for _ in range(L)]
    visited[sl][sr][sc] = 1
    Q = deque([(sl, sr, sc)])
    while Q:
        l, r, c = Q.popleft()
        for d in range(6):
            nl = l + dl[d]
            nr = r + dr[d]
            nc = c + dc[d]
            # 범위 밖이거나
            if not (0 <= nl < L and 0 <= nr < R and 0 <= nc < C):
                continue
            # 이미 방문했거나 벽이면
            if visited[nl][nr][nc] or B[nl][nr][nc] == "#":
                continue
            # 도착지면 출력 후 리턴
            if B[nl][nr][nc] == "E":
                print("Escaped in {} minute(s).".format(visited[l][r][c]))
                return
            # 가능한 다음 위치에 거리 표시하고 큐에 담기
            visited[nl][nr][nc] = visited[l][r][c] + 1
            Q.append((nl, nr, nc))
    
    print("Trapped!")   # 불가능한 경우

while True:
    L, R, C = map(int, input().split())
    if (L, R, C) == (0, 0, 0):
        break
    B = []      # 빌딩 3차원 배열로 표현
    sl, sr, sc = -1, -1, -1     # 시작 좌표
    for l in range(L):
        B.append([list(input().rstrip()) for _ in range(R)])
        for r in range(R):
            for c in range(C):
                if B[l][r][c] == "S":
                    sl, sr, sc = l, r, c
        input()
    bfs()

---

• 시간 : 184ms / 메모리 : 128252kb
• 고찰 : 바보같이 답 잘 구해놓고 "Escaped in 11 minute(s)." 문장 출력할 때 마지막 "."을 안 찍어서 한 번 틀렸다 ㅋㅋ 이렇게 문장 출력하는 건 실수할 수 있으니 타이핑하지 말고 그냥 복붙하자ㅠㅠ 깔끔한 BFS 문제라 크게 고민하지 않고 풀어냈다. 다만 인풋 받는게 한 번에 안 받아져서 애를 먹었다,,ㅎ 너무나 쉬운 것을^^ 3차원 배열이라고 다를 게 없다. 그냥 범위 고려할 것(층)이 하나 더 늘었다고 생각하면 쉽다. 더불어 시간 2위 달성했다! Keep Going!