Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- 플로이드 와샬
- 다익스트라
- SWEA
- 크루스칼
- 2021 KAKAO BLIND RECRUITMENT
- 2020 KAKAO BLIND RECRUITMENT
- 비트마스킹
- 백준
- 2019 KAKAO BLIND RECRUITMENT
- 트라이
- GIT
- 2020 카카오 인턴십
- 구현
- 투 포인터
- 프로그래머스
- Spring
- 로봇 청소기
- 이분탐색
- 조합
- 스택
- 파이썬
- 우선순위큐
- 2018 KAKAO BLIND RECRUITMENT
- 투포인터
- 백트래킹
- BFS
- 시뮬레이션
- 플로이드와샬
- 브루트포스
- 최소 신장 트리
Archives
- Today
- Total
개발조아
[BOJ/백준] 6593 상범빌딩 파이썬 본문
728x90
문제 링크 : https://www.acmicpc.net/problem/6593
6593번: 상범 빌딩
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어
www.acmicpc.net
평범한 3차원 공간에서의 BFS이다.
S에서 출발하여 E까지 가는데 걸리는 최단시간을 구하는 것이다.
from sys import stdin
from collections import deque
input = stdin.readline
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]
def solv():
while True:
global l,r,c,board
l,r,c = map(int, input().split())
if l == r == c == 0:
return
sz=sx=sy=-1
board = []
for z in range(l):
board.append([input().strip() for _ in range(r)])
if sz == -1:
for x in range(r):
for y in range(c):
if board[z][x][y] == 'S':
sz,sx,sy = z,x,y
break
if sz != -1:
break
input()
answer = bfs(sz,sx,sy)
if answer >= 0:
print('Escaped in %d minute(s).'%(answer))
else:
print('Trapped!')
def bfs(sz,sx,sy):
visited = [[[False]*c for _ in range(r)]for _ in range(l)]
visited[sz][sx][sy] = True
q = deque([(sz,sx,sy,0)])
while q:
z,x,y,cnt = q.pop()
if board[z][x][y] == 'E':
return cnt
for d in range(6):
nz = z + dz[d]
nx = x + dx[d]
ny = y + dy[d]
if point_validator(nz,nx,ny,visited):
visited[nz][nx][ny] = True
q.appendleft((nz,nx,ny,cnt+1))
return -1
def point_validator(z,x,y,visited):
if z < 0 or x < 0 or y < 0 or z >= l or x >= r or y >= c:
return False
elif board[z][x][y] == '#':
return False
elif visited[z][x][y]:
return False
return True
solv()
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ/백준] 22234 가희와 은행 파이썬 (0) | 2021.08.24 |
---|---|
[BOJ/백준] 2917 늑대 사냥꾼 파이썬 (0) | 2021.08.23 |
[BOJ/백준] 1325 효율적인 해킹 파이썬 (0) | 2021.08.22 |
[BOJ/백준] 18808 스티커 붙이기 파이썬 (0) | 2021.08.20 |
[BOJ/백준] 16985 Maaaaaaaaaze 파이썬 (0) | 2021.08.19 |