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 | 31 |
Tags
- N과M
- MYSQL
- 다이나믹 프로그래밍
- 프로그래머스
- 스택
- 브루트포스
- 힙
- 가상메모리
- python
- level1
- 다익스트라
- 수학
- level2
- 파이썬
- 백준
- 구현
- dict
- 딕셔너리
- DP
- level3
- programmers
- 운영체제
- 가상메모리 관리
- 재귀
- BOJ
- 그리디
- 코딩테스트
- level0
- BFS
- dfs
Archives
- Today
- Total
동캄의 코딩도장
백준 7569 [토마토] 파이썬 본문
https://www.acmicpc.net/problem/7569
# 백준 7569
from collections import deque
import sys
dr = [0, 1, -1, 0, 0, 0]
dc = [1, 0, 0, -1, 0, 0]
dh = [0, 0, 0, 0, 1, -1]
input = sys.stdin.readline
M, N, H = map(int, input().split())
field = [[[0]*(M) for _ in range(N)] for _ in range(H)]
tomatos = []
for k in range(H):
for j in range(N):
s = list(map(int, input().split()))
for i in range(M):
if s[i] == 1:
tomatos.append([k, j, i])
field[k][j][i] = s[i]
def bfs(tomatos):
q = deque([])
for tomato in tomatos:
q.append(tomato)
while q:
pos = q.popleft()
for i in range(6):
m = pos[2]+dc[i]
n = pos[1]+dr[i]
h = pos[0]+dh[i]
if 0 <= m < M and 0 <= n < N and 0 <= h < H and field[h][n][m] != -1 and (field[h][n][m] == 0 or field[h][n][m] > 1+field[pos[0]][pos[1]][pos[2]]):
field[h][n][m] = 1+field[pos[0]][pos[1]][pos[2]]
q.append([h, n, m])
bfs(tomatos)
answer = 0
check = 0
for k in range(H):
for j in range(N):
for i in range(M):
if field[k][j][i] == 0:
check = 1
break
else:
answer = max(answer, field[k][j][i])
if check == 1:
break
if check == 1:
break
if check == 1:
print(-1)
else:
print(answer-1)
bfs를 사용하여 해결하였다. (3차원 배열 접근 --> arr[높이][세로][가로] 임을 기억하자!)
(pypy3로 해결하였습니다. python3 에서는 시간초과)
# 백준 7569 python3 통과
from collections import deque
import sys
dr = [0, 1, -1, 0, 0, 0]
dc = [1, 0, 0, -1, 0, 0]
dh = [0, 0, 0, 0, 1, -1]
input = sys.stdin.readline
M, N, H = map(int, input().split())
field = [[[0]*(M) for _ in range(N)] for _ in range(H)]
tomatos = []
for k in range(H):
for j in range(N):
s = list(map(int, input().split()))
for i in range(M):
if s[i] == 1:
tomatos.append([k, j, i])
field[k][j][i] = s[i]
def bfs(tomatos):
q = deque([])
for tomato in tomatos:
q.append(tomato)
while q:
pos = q.popleft()
for i in range(6):
m = pos[2]+dc[i]
n = pos[1]+dr[i]
h = pos[0]+dh[i]
if 0 <= m < M and 0 <= n < N and 0 <= h < H and field[h][n][m] != -1 and field[h][n][m] == 0:
field[h][n][m] = 1+field[pos[0]][pos[1]][pos[2]]
q.append([h, n, m])
bfs(tomatos)
answer = 0
check = 0
for k in range(H):
for j in range(N):
for i in range(M):
if field[k][j][i] == 0:
check = 1
answer = max(answer, field[k][j][i])
if check == 1:
print(-1)
else:
print(answer-1)
상자의 위치 값이 0이라면(방문하지 않았다면) 값을 더하면 되므로, 값을 비교하는 연산은 필요가 없다.
(python3 통과)
--> 조그만한 시간차이도 중요하다!
'코테 > BOJ' 카테고리의 다른 글
백준 15686 [치킨배달] 파이썬 (0) | 2022.04.16 |
---|---|
백준 14502 [연구소] 파이썬 (0) | 2022.04.15 |
백준 16928 [뱀과 사다리 게임] 파이썬 DFS BFS (0) | 2022.04.14 |
백준 14500 [테트로미노] 파이썬 (0) | 2022.04.14 |
백준 10026 [적록색약] 파이썬 (0) | 2022.04.14 |