Sign in Subscribe
PS

[PS] BOJ 30508 / 고인물이싫어

Minjun Kim

• 5 min read
[PS] BOJ 30508 / 고인물이싫어
Thumbnail: Photo by Sergio Cima (Unsplash)
문제 링크: https://www.acmicpc.net/problem/30508

그래프 탐색과 누적합을 모두 활용하는 문제입니다. 풀이를 떠올리면 구현은 어렵지 않습니다.

풀이

단계별로 생각하기

  1. 하수구에서부터 BFS 진행해서 전체 타일에 물이 빠진 칸 파악하기
  2. 누적합 계산해서 (r, c) 지점까지 물이 빠진 칸의 수 세기
  3. H x M 크기로 모두 물이 빠진 칸이 몇 개 존재하는지 계산하기

단계별로 문제를 나눠서 풀면 쉽게 답을 구할 수 있습니다.

1) 물이 빠진 칸 파악하기 (BFS)

처음 주어지는 입력의 모든 칸은 물에 차 있습니다. 이후, 하수구의 좌표가 주어집니다.

어떤 칸은 자신보다 높이가 같거나 낮은 칸이 물이 빠져 있거나 or 하수구일 때만 물이 빠집니다. 이를 반대로 생각하면, 하수구에서 시작해 자신보다 높이가 같거나 높은 방향의 모든 칸의 물을 빼면 물이 빠진 칸을 모두 찾아낼 수 있습니다.

하수구 좌표가 주어질 때 마다, bfs를 통해 물이 빠지는 칸을 탐색하는 방식으로 구현했습니다.

  • 입력 배열 tiles는 이후 누적 합 계산 등에 맞추기 위해, $(N + 1) \times (M + 1)$ 크기로 선언되었습니다.
  • 방문 여부를 기록하는 배열은 drained입니다. 정확히는, 각 칸이 물이 빠졌는지의 유무를 기록합니다.
    • 이전 탐색에서 물이 안 빠졌던 칸도 다시 탐색할 경우 물이 빠질 수 있으니, 탐색 과정에서 물이 빠지는 칸만 True로 기록합니다.
from collections import deque

NEXT_POS = ((1, 0), (0, 1), (-1, 0), (0, -1))
N, M = map(int, input().split())
H, W = map(int, input().split())
tiles = [[None] for _ in range(N + 1)]
drained = [[False] * (M + 1) for _ in range(N + 1)]
queue = deque()

# 0. 입력 받기
for i in range(1, N + 1):
    tiles[i].extend(map(int, input().split()))

def bfs(r, c):
    queue.clear()
    queue.append((r, c))
    drained[r][c] = True
    while queue:
        r, c = queue.popleft()
        for dr, dc in NEXT_POS:
            nr = r + dr
            nc = c + dc
            if 1 <= nr <= N and 1 <= nc <= M and not drained[nr][nc] and tiles[nr][nc] >= tiles[r][c]:
                drained[nr][nc] = True
                queue.append((nr, nc))

BFS로 물이 빠지는 칸 찾기

2) 누적 합 계산하기

이제 물이 빠진 칸의 개수를 누적 합으로 기록해야 합니다. 누적 합을 사용하면, 이후 $H \times W$ 크기의 칸이 모두 물이 빠져 있는 경우의 수를 빠르게 셀 수 있기 때문입니다.

2차원 배열의 형태이므로, 누적 합을 통해 $(r, c)$부터 $H \times W$ 만큼의 공간에 담긴 누적 합의 결과값을 구하는 식은 다음과 같습니다. 관련한 설명은 이전에 비슷한 문제에서도 다뤘으니 해당 글을 참고해 주세요.

prefix[r + H - 1][c + W - 1] - prefix[r - 1][c + W - 1] - prefix[r + H - 1][c - 1] + prefix[r - 1][c - 1]

누적 합을 활용해 H x W 크기의 공간을 검사하는 식

prefix = [[0] * (M + 1) for _ in range(N + 1)]

# 2. 누적합 계산해서 (r, c) 지점까지 물이 빠진 칸의 수 세기
for r in range(1, N + 1):
    for c in range(1, M + 1):
        prefix[r][c] = prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1] + (1 if drained[r][c] else 0)

누적 합 계산하기

3) 누적 합을 활용해 가능한 경우의 수 세기

앞선 누적 합 계산식을 통해, $(r, c)$로부터 $H \times W$ 크기의 칸 안에 물이 빠진 칸의 개수를 구합니다. 이 칸의 개수가 $H \times W$와 같다면 물에 젖지 않고 땅을 디딜 수 있으므로 count를 1 증가시킵니다.

# 3. H x M 크기로 모두 물이 빠진 칸이 몇 개 존재하는지 계산하기
size = H * W
count = 0
for r in range(1, N - H + 2):
    for c in range(1, M - W + 2):
        drained_tiles = prefix[r + H - 1][c + W - 1] - prefix[r - 1][c + W - 1] - prefix[r + H - 1][c - 1] + prefix[r - 1][c - 1]
        if drained_tiles >= size:
            count += 1

print(count)

답 구하기

전체 코드

from collections import deque
input = open(0).readline

NEXT_POS = ((1, 0), (0, 1), (-1, 0), (0, -1))
N, M = map(int, input().split())
H, W = map(int, input().split())
tiles = [[None] for _ in range(N + 1)]
drained = [[False] * (M + 1) for _ in range(N + 1)]
prefix = [[0] * (M + 1) for _ in range(N + 1)]
queue = deque()

# 0. 입력 받기
for i in range(1, N + 1):
    tiles[i].extend(map(int, input().split()))

def bfs(r, c):
    queue.clear()
    queue.append((r, c))
    drained[r][c] = True
    while queue:
        r, c = queue.popleft()
        for dr, dc in NEXT_POS:
            nr = r + dr
            nc = c + dc
            if 1 <= nr <= N and 1 <= nc <= M and not drained[nr][nc] and tiles[nr][nc] >= tiles[r][c]:
                drained[nr][nc] = True
                queue.append((nr, nc))
    
# 1. 하수구에서부터 BFS 진행해서 전체 타일에 물이 빠진 칸 파악하기
for _ in range(int(input())):
    r, c = map(int, input().split())
    bfs(r, c)

# 2. 누적합 계산해서 (r, c) 지점까지 물이 빠진 칸의 수 세기
for r in range(1, N + 1):
    for c in range(1, M + 1):
        prefix[r][c] = prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1] + (1 if drained[r][c] else 0)

# 3. H x M 크기로 모두 물이 빠진 칸이 몇 개 존재하는지 계산하기
size = H * W
count = 0
for r in range(1, N - H + 2):
    for c in range(1, M - W + 2):
        drained_tiles = prefix[r + H - 1][c + W - 1] - prefix[r - 1][c + W - 1] - prefix[r + H - 1][c - 1] + prefix[r - 1][c - 1]
        if drained_tiles >= size:
            count += 1

print(count)

solution.py