코딩테스트 스터디-7576 토마토
시리즈 공지
지난번 공지에서 말했듯이, 현재 부트캠프를 다니며 뜻이 맞는 사람들(?)과 코딩테스트 연습을 하고 있습니다.
매주 3문제씩을 풀고 그것을 github 레포지토리에 각자 브랜취로 공유해, 주말 함께 코드리뷰를 진행하는 방식입니다.
이번에는 1주차 풀었던 문제를 공유해보겠습니다.
간단히 알고리듬만 설명하는 식으로 진행할게요~
ACMICPC 7576 토마토
1
2
3
4
5
6
7
8
9
10
11
12
13
14
토마토를 창고에 보관하는 격자모양의 상자들의 크기와
익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때,
며칠이 지나면 토마토들이 모두 익는지,
그 최소 일수를 구하는 프로그램을 작성하라.
단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다.
M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.
단, 2 ≤ M,N ≤ 1,000 이다.
둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다.
즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다.
하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.
정수 1은 익은 토마토, 정수 0은 익지 않은 토마토,
정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
설명
문제를 보면 알겠지만, 대놓고 BFS로 풀어라 말하는 문제이다. DFS는 안되는 게, 문제에 하루가 지나면 상하좌우의 모든 토마토가 익는다라 쓰여 있어 한쪽부터 깊이 파고드는 DFS로는 시간 계산이 불가능하기 때문이다.
여기서 한번 더 꼬아 막혀진 칸도 있어 모든 칸에 도달할 수 없는 경우도 있고, 시작지점이 여러개가 있어 동시 계산해야 한다!
풀이법
아래는 파이썬으로 작성한 코드~
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#시간 구해야 하니 BFS로 풀어야
from collections import deque
#인자값입력
n,m = map(int,input().split())
tomato = []
for i in range(m):
tomato.append(list(map(int,input().split())))
#탐색할때 쓸 배열(상하좌우탐색)
karo = [0,0,1,-1]
sero = [1,-1,0,0]
#탐색함수
def solution(chogi):
# BFS에 쓸 큐 생성(visited는 방문 확인)
queue = deque([])
visited = set([])
# 큐에 초기 익은토마토 위치 넣기
# queue의 0은 최초 시간
for i in chogi:
a,b = i
queue.append((a,b,0))
visited.add((a,b))
# 시간변수
ee = 0
# 다들 아는대로 BFS탐색 진행
while queue:
x, y, z = queue.popleft()
# 초기 익은토마토가 여러개일때는 가장 늦게 전부 탐색된 토마토 시간 기준이 되어야 하므로 최대값
ee = max(z,ee)
for i in range(4):
nx = x + karo[i]
ny = y + sero[i]
if 0 <= nx < len(tomato) and 0 <= ny < len(tomato[0]):
if (nx, ny) not in visited and tomato[nx][ny] == 0:
visited.add((nx, ny))
# 탐색 완료이므로 시간에 1 추가
queue.append((nx, ny, z+1))
#
return ee, len(visited)
# 초기 익은토마토들이 담길 변수
# 전부 익는 시간 계산이므로 한번에 전부 BFS 돌아야해
chogi = set([])
# 막힌 칸 개수가 담긴 변수
minuscount = 0
for i in range(m):
for j in range(n):
if tomato[i][j] == 1:
chogi.add((i,j))
elif tomato[i][j] == -1:
minuscount += 1
# q는 시간, w는 탐색된 칸 개수
q,w = solution(chogi)
# 전체 칸개수에서 막힌칸 뺀 게 탐색한칸과 다르면 못다다른 칸이 있다는 뜻
if w!=((m*n)-minuscount):
print(-1)
else:
print(q)
BFS를 수행하는 solution 함수에 주목
시작지점이 여러개일 경우, 한 번에 모두를 수행해야 하므로 시작지점을 chogi 배열에 넣어 solution 함수에 전달
solution에서는 우선 chogi에 있는 모든 것을 BFS 큐에 넣고, BFS 큐의 요소는 좌표만 아닌 해당 위치에 도달 시의 시간도 넣어
(그래야 시간계산가능, 당연히 시작지점은 0)BFS 탐색(while queue)는 기존과 동일하지만 시작지점이 여러개일 경우 전체 시간은 가장 늦게 도달한 시작지점의 시간이 되어야 하므로 해당 부문 처리
마지막으로 전부 도달 여부 판단: 전체 칸 수(가로*세로-막혀있는칸)과 BFS함수에서 체크한 방문칸 개수(len(visited))를 비교, 안 같으면 전체 도달 못했으니까 -1, 아니면 아까 계산한 시간!
후기
난이도는 살짝 대기업 코딩테스트 1번 문제로 나올 정도였다. 뭐 회사마다 다르겠지만…