Ray`s Tech Lab

https://www.acmicpc.net/problem/2468

무식하게 풀어보자.

2차원 배열 형태로 필드가 주어졌을 때, 비의 양을 0부터 100까지 해주면서 생기는 영역의 개수를 하나하나 세보면 된다. 영역의 개수를 세는 것은 N * N짜리 필드의 칸들을 하나하나 순회하면서 센다고 할 때, N으로 가능한 최댓값은 100이므로 이론상 최악의 경우 100 * 100 * 100 = 100만번 정도의 계산을 하게 된다. 문제의 제한시간은 1초인데 파이썬은 1초 내에 충분히 100만번의 연산이 가능하므로 통과할 수 있으리라 어림짐작이 가능하다.

조금만 더 최적화시켜서, 비의 양을 굳이 0부터 100까지 순회할 필요는 없다. 비의 양이 0이면 안전영역의 개수는 무조건 1이고(각 영역의 높이는 무조건 1이상이므로), 비의 양이 주어진 필드의 최고높이가 되는 순간 모든 지역이 물에 잠겨 안전영역의 개수는 0이 된다. 따라서 비의 양을 0 ~ 100까지가 아니라 1 ~ 필드에서 주어진 최고높이까지만 순회하면 됨

import sys
sys.setrecursionlimit(10000)

N = int(sys.stdin.readline())
height, checked = [], []

for _ in range(N):
    height.append(list(map(int, sys.stdin.readline().split())))
    checked.append([True] * N)

# 인접한 영역들 싹 다 표시하기
def checkArea(N, r, c):
    checked[r][c] = False
    directions = [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]
    for nr, nc in directions:
        if (0 <= nr < N) and (0 <= nc < N) and checked[nr][nc]:
            checkArea(N, nr, nc)  


# 빗물의 높이가 rain으로 주어졌을 때 안전영역 개수 계산
def calculate(N, rain):
    areas = 0
    # 잠기는 영역들 구하기 - False로 표현
    for r in range(N):
        for c in range(N):
            if rain >= height[r][c]:
                checked[r][c] = False
            else:
                checked[r][c] = True
    # 안전 영역 개수 구하기
    for r in range(N):
        for c in range(N):
            if checked[r][c]:
                checkArea(N, r, c)
                areas += 1
    return areas


# 안전영역의 최대 개수 리턴
def solution(N):
    # 답이 될 수 있는 값의 최소 = 1 (각 지점 높이 최소 = 1, 빗물 최소높이 = 0이므로)
    answer = 1
    for rain in range(1, 101):
        areas = calculate(N, rain)
        # 만약 특정 빗물 높이에 대해 안전영역이 0이면 break -> 빗물이 height의 최댓값과 같아진 거니까
        if areas == 0:
            break
        if answer < areas:
            answer = areas
    return answer

print(solution(N))

인접한 영역을 어떻게 셀 것인가에 대해 고민해본 문제다. 이는 재귀를 통해 방문한 지역들을 모두 방문처리(본 코드에선 cheked배열을 이용)하는 것으로 구현했다. 어떤 지점으로부터 상하좌우방향으로 1칸씩 이동하며 순회해야 할 때, checkArea함수에서 쓴 것처럼 방향배열을 설정해두고 사용하면 매우 편리하다. 아니면 다음처럼 해도 편리한 것 같다. 스터디에서 다른 스터디원이 쓰는 걸 참고했음ㅋㅋ

# global하게 방향배열 만들기
direction = [(0, -1), (0, 1), (-1, 0), (1, 0)]

# 어딘가에서 만든 함수에서 이용
def some_func(r, c):
	...
    for dr, dy in direction:
        nr = r + dr                               # 다음 row좌표구하기
        nc = c + dc                               # 다음 col좌표구하기
        ...

왜 이문제가 DFS, BFS분류에도 들어가는지 궁금했는데, 현재 위치에서 상하좌우에 있는 칸 중 잠기지 않은 칸들을 그래프처럼 표기할 수 있겠다는 생각이 든다. 그러면서 방문여부를 따지면서 "전에 방문한 적 있네? 그럼 넌 안 봐"하면서 따지니까 굳이 따지자면 내가 한 방식은 DFS인 듯.