백준 7576 토마토, 7569 토마토, 17114 하이퍼 토마토 문제 풀이
백준 온라인 저지, 7576번: 토마토, 7569번: 토마토, 17114번: 하이퍼 토마토
도입
백준 온라인 저지의 토마토 문제는 격자 공간에서의 BFS, DFS 탐색을 다루는 대표적인 문제이다. 기본적으로는 <7576번: 토마토>, <7569번: 토마토>, 그리고 <17114번: 하이퍼 토마토> 문제는 처리할 격자 공간의 차원만 다를 뿐 동일한 접근으로 해결할 수 있다.
이 문제에서 주어지는 입력 유형에서 인접 행렬을 생성하는 것은 비효율적이다. 각 격자점은 아무리 많아도 인접한 4개(2차원), 혹은 6개(3차원)의 격자점 외에는 모두 연결될 수 없다.
대신 격자 공간 자체를 다음 위치로의 전이에 사용할 수 있다.
1
2
3
4
5
6
7
# 2차원 격자 공간
y: int
x: int
for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
ny, nx = y + dy, x + dx
현재 탐색하고 있는 격자점의 좌표 $(y, x)$와 인접한 격자점 $(ny, nx)$를 for문을 통해 생성한 $(\Delta y, \Delta x)$를 이용하여 순차적으로 계산할 수 있다.
7576번: 토마토 (2차원 공간)
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
def compute(field: list, N: int, M: int, tomatoes: list) -> int:
q = deque()
for tomato in tomatoes:
q.append(tomato)
while q:
y, x = q.popleft()
for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
ny, nx = y + dy, x + dx
if not (0 <= ny < N and 0 <= nx < M):
continue
if field[ny][nx] == -1:
continue
if field[ny][nx] != 0:
continue
field[ny][nx] = field[y][x] + 1
q.append((ny, nx))
set_field = set()
for row in field:
set_field.update(row)
if 0 in set_field:
return -1
return max(set_field) - 1
compute 함수는 BFS를 구현하였다. 이 함수는 $(M, N)$의 격자 공간에 대한 데이터 field와 최초 시점에 익어있는 토마토(=공간 상에서 데이터가 1)의 위치 정보 tomatoes를 받는다.
BFS 로직이 처리 중인 $(y, x)$ 위치에서 다음 위치로 전이하기 위해, for문 안의 반복 과정에서 다음 위치인 $(ny, nx)$를 생성하고 세 번의 조건문 처리에 걸쳐서 유효성을 검사한다.
*두 번째 조건문 field[ny][nx] == -1과 세 번째 조건문은 field[ny][nx] != 0은 세 번째 조건문으로 동치할 수 있다. 다만 이번 구현에서는 == -1은 빈 공간, != 0은 익지 않은 토마토임을 순차적으로 생각하도록 두 조건 모두 유지하였다.
이 풀이에서 BFS 처리를 위한 구현이 아닌 부분, field[ny][nx] = field[y][x] + 1에서 문제가 요구하는 내용을 처리한다. 최적화를 위해 데이터 표현 면에서 문제에서의 정의와 이 풀이에서의 임의 정의를 혼용했다.
문제의 원본 데이터에서 -1은 빈 공간, 0은 익지 않은 토마토, 1은 익은 토마토였다. 토마토가 익은 시점을 따로 관리하는 것도 괜찮은 선택이나, 이미 $NM$ 크기로 생성된 정수 배열이 존재한다. 심지어 $2^{32}$개 값을 갖는 전체 정수 공간에서 단 3개의 값만 의미를 갖는다.
그래서 위 풀이에서는 모든 자연수 범위를 갖는 격자를 익은 토마토로 간주하고, 개별 자연수는 익은 시점이라는 정의를 임의대로 도입했다. 위 코드에서 $(y, x)$ 위치의 격자점 field[y][x] 값 중 자연수 값은 토마토가 익은 시점 + 1로 정의된다.
만약 모든 토마토가 익었다면 값이 0인 격자점은 존재할 수 없다. BFS가 종료되면 격자 공간 상의 값 내에 0이 있는지 검사하여 -1을 출력해야 하는지, 혹은 모든 토마토가 익은 시점을 출력해야하는지 결정할 수 있다.
3차원과 11차원으로의 확장
3차원과 11차원에서의 처리도 크게 다르지 않다. 늘어난 격자 공간의 차원만큼 반복 과정과 배열의 차원만 늘려 처리하면 된다.
7569번: 토마토 (3차원 공간)
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
def compute(field: list, H: int, N: int, M: int, tomatoes: list) -> int:
q = deque()
for tomato in tomatoes:
q.append(tomato)
while q:
z, y, x = q.popleft()
for dz, dy, dx in [(-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1)]:
nz, ny, nx = z + dz, y + dy, x + dx
if not (0 <= nz < H and 0 <= ny < N and 0 <= nx < M):
continue
if field[nz][ny][nx] == -1:
continue
if field[nz][ny][nx] != 0:
continue
field[nz][ny][nx] = field[z][y][x] + 1
q.append((nz, ny, nx))
set_field = set()
for plane in field:
for row in plane:
set_field.update(row)
if 0 in set_field:
return -1
return max(set_field) - 1
2차원 공간에서의 토마토 문제와 비교하여 축선을 하나 더 도입한 것 외에는 동일한 내용으로 구현할 수 있다.
17114번: 하이퍼 토마토
하이퍼 토마토 문제는 3차원으로부터 새 좌표축을 8개 더 추가하여 11개 차원을 처리하게 함으로써 해결할 수 있다. 2차원 공간에서 3차원 공간으로 확장할 때 축선을 한 개 더 추가했던 것을 동일하게 적용한다.
1
field = [[[[[[[[[[list(map(int, input().split())) for _n in range(N)] for _o in range(O)] for _p in range(P)] for _q in range(Q)] for _r in range(R)] for _s in range(S)] for _t in range(T)] for _u in range(U)] for _v in range(V)] for _w in range(W)]
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
while q:
now = q.popleft()
now_value = field[now[0]][now[1]][now[2]][now[3]][now[4]][now[5]][now[6]][now[7]][now[8]][now[9]][now[10]]
new_value = now_value + 1
is_processed = False
for dt in DT:
new = [now[i] + dt[i] for i in range(11)]
if not (
0 <= new[0] < W and
0 <= new[1] < V and
0 <= new[2] < U and
0 <= new[3] < T and
0 <= new[4] < S and
0 <= new[5] < R and
0 <= new[6] < Q and
0 <= new[7] < P and
0 <= new[8] < O and
0 <= new[9] < N and
0 <= new[10] < M
):
continue
# if field[new[0]][new[1]][new[2]][new[3]][new[4]][new[5]][new[6]][new[7]][new[8]][new[9]][new[10]] == -1:
# continue
if field[new[0]][new[1]][new[2]][new[3]][new[4]][new[5]][new[6]][new[7]][new[8]][new[9]][new[10]] != 0:
continue
field[new[0]][new[1]][new[2]][new[3]][new[4]][new[5]][new[6]][new[7]][new[8]][new[9]][new[10]] = new_value
raw_tomato_counts -= 1
q.append(new)
is_processed = True
if is_processed:
if elapsed < new_value:
elapsed = new_value
하이퍼 토마토 문제는 구데기 컵이라는 대회에 출제된 문제여서, BFS DFS 알고리즘을 연습하기보다는 넌센스 문제에 조금 더 가까운 성격을 갖는다. 때문에 런타임이 무거운 파이썬 코드로 통과하기 위해서는, 11차원의 탐색 설계도 중요하지만 최대한의 최적화 처리도 필요하다.
참고 사항으로, 이전에 이 문제 질문 게시판에 <파이썬에서 시간 확보하는 전략들>이라는 제목으로 파이썬에서의 최적화 전략을 작성한 적이 있었다.
- 최대한 빠른 입출력 사용
sys.stdin.readline대신iter(open(0).read().split('\n')).__next__
- 함수 호출 최소화
- 함수 호출은 콜 스택을 처리, 코드 흐름 전환 등의 이유로 성능 저하의 원인이 된다.
- 전체 탐색 지양
- 2차원, 3차원 풀이에서는 결과 출력을 위해
set_field: set을 사용하여 익지 않은 토마토가 있는지 파악했다. 하지만 이 역시 이미 한 번 탐색한 격자 공간을 재탐색해야한다. - 11차원 풀이에서는 익지 않은 토마토의 개수를 표현하는
raw_tomato_counts를 추가하고, 실제 격자 공간에서의 데이터 상황과 관계없이 탐색 과정 상에서raw_tomato_counts -= 1하여 대응했다.
- 2차원, 3차원 풀이에서는 결과 출력을 위해
- 튜플 사용 지향
- 인접한 격자점으로 전이하기 위해 사용하는
for dy, dx in dt에서dt는 불변한다. 이러한 경우에는 리스트 대신 튜플을 사용했다. - 참조: <Are tuples more efficient than lists in Python?>
- 인접한 격자점으로 전이하기 위해 사용하는
- 리스트
append사용 지양- 11차원 데이터를 입력받는 과정에서, 각 줄을 차례로 받아
append를 연달아 호출하는 것보다는field = [[[[[[[[[[list(map(int, input().split())) for _n in range(N)] ... for _w in range(W)]로append호출을 최대한 피했다. append를 사용해야만 하지만 덱 기능을 사용하지는 않는 경우에, 리스트와 덱 중 어느 것이 더 우위가 있는지도 확인해보았다. 두 자료형 사이에 차이는 확인되지 않았다:1 2 3 4
❯ python -mtimeit -s 'from collections import deque' -s 's = []' -s 'for _i in range(int(1e7)): s.append(0)' 100000000 loops, best of 5: 3.79 nsec per loop ❯ python -mtimeit -s 'from collections import deque' -s 's = deque()' -s 'for _i in range(int(1e7)): s.append(0)' 100000000 loops, best of 5: 3.79 nsec per loop
- 11차원 데이터를 입력받는 과정에서, 각 줄을 차례로 받아