Ray`s Tech Lab

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

문제 요약

A장의 카드더미와 B장의 카드더미를 합칠 때는 A+B번의 비교를 한다.

여러 카드더미들이 주어졌을 때, 모든 카드가 합쳐진 더미를 만들 때 비교횟수는 어떤 순서로 카드들을 합쳐나가는지에 따라 달라진다. 이 때 최소 비교횟수는 몇인가?

순서는 임의대로 할 수 있기 때문에 카드가 나열된 순서와는 관계가 없다. 또한 카드더미의 개수가 1개만 주어질 때도 있는데 이 경우 비교횟수는 0이 됨을 알아두자.

1. 일단, 무식하게 풀어본다면?

나올 수 있는 모든 비교횟수합들을 구해서 가장 작은 값을 취하면 된다. n개의 카드더미가 있을 때, 이 중 두 더미를 골라 합치므로 가짓수는 nC2개. 이렇게 두 개를 골라 합치면 하나의 카드더미가 만들어지는 것이므로, 남은 카드더미는 n-1개가 되며 여기서 다시 2개를 골라 합친다. 즉 나올 수 있는 모든 비교횟수합은 nC2 * n-1C2 * n-3C2 * ...번이며 n은 최대 100,000이므로 문제의 제한시간인 2초 내에 통과하는 것은 힘들다. 즉 다른 방법을 모색해볼 것.

2. dp나 그리디를 의심해보자

>> 2-1. 최적부분구조를 가지는가?

Yes. n개의 카드묶음들로부터 나올 수 있는 최소비교횟수는 n개의 카드 중 2개를 골라 얻는 비교횟수와 그로부터 만들어지는 n-1개의 카드묶음들로부터 나오는 최소합 중(즉 nC2개가 있을 것이다) 가장 작은 값이 된다.

ex) 1번 더미와 2번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값2번 더미와 3번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값이런 것들 중 가장 작은 값이 문제가 요구하는 답이 됨

>> 2-2. 중복되는 구조가 있는가?

Sometimes Yes. k개 만큼의 카드더미가 있다고 할 때, 각각의 카드더미들의 구성이 같다면 중복된다고 판단가능. 그러나 이렇게 중복되는 상황이 항상 나올 것이라고 보장할 수 없다. 가끔 중복되는 정도라고 생각된다.

즉 DP로 접근하는 것은 그닥 효율적으로 보이진 않는다.

>> 2-3. 합법적으로 시작하는 그리디 의심. 탐욕적 선택 속성이 있는가?

사실 이 문제는 그리디 티를 팍팍 내는 문제라고 생각되며, 직관적으로 가장 작은 카드더미들부터 합치는 것이 좋을 것이라는 냄새도 솔솔 풍기는 문제지 않나 싶다. 문제에서 보여주는 예시부터 가장 작은 애들부터 합치니까. 실제로 이 문제는 가장 작은 카드더미부터 합쳐나가야 정답을 얻는다. 그러나 실전도 아니고 이렇게 연습 삼아 푸는 문제들에선 엄밀하게 그리디임을 검증하고 넘어가는 것이 좋을 것이다.그럼, 왜 그리디라고 생각했을까?

근거1. 탐욕적 선택 속성이 있다 즉 어떤 페이즈에서 내린 선택이 그 다음 페이즈의 선택에 영향을 주지 않는다.

내가 이번 페이즈의 선택에서 가장 작은 걸 취했다고 해서 다음 선택에서 가장 작은 걸 취할 수 없는 그런 상황은 없다. 늘 가장 작은 걸 취할 수 있다. 그리디 속성이 있다면 이렇게 내가 현재 내리는 선택이 이후의 선택에 영향을 주지 않는다. 살짝 헷갈렸던 것은, 내가 지금 선택하는 카드더미에 따라 다음 페이즈에 선택하는 카드더미의 구성이 달라지므로 "이 상황은 내가 지금 내리는 선택이 뒤에 영향을 주는 상황이 아닌가?"했지만, 정확히는 뒤에 내리는 선택에 영향을 주지 않는다가 맞지 않나 싶다. 이 문제를 통해 배웠음. 예를 들어 1309번 동물원 문제의 경우, 내가 왼쪽에 있는 칸에 사자를 배치하기로 했으면 다음 줄의 왼쪽 칸에는 사자를 배치할 수 없다는 식으로 내가 현재 내린 선택이 뒤의 선택에 영향을 주는 부분이 존재했다. 암튼 간에 이 1715번 카드 정렬하기 문제는 내가 현재 페이즈에서 내리는 선택에 다음번 페이즈에서 내리는 선택에 영향을 주지 않으므로 그리디 속성이 있다고 볼 수 있다.

근거2. 그리디는 한 번의 선택들이 그 자체로 부분문제가 된다.

스터디에서 배운 그리디의 특성이다. 제일 작은 것 2개를 고른다고 할 때, 내가 고른 두 개의 카드더미들로 인해 하나의 카드더미가 새로 만들어지고, 그 n-1개의 카드더미들로부터 또 2개를 고른다는 부분문제가 된다. 즉 한 번의 선택들이 그 자체로 부분문제가 되는 속성 역시 찾아볼 수 있었다.

3. 그렇다면, 그리디의 정당성 검증은?

지금 나는 처음에 가장 작은 카드더미들을 고른 경우를 포함하는 최적해가 있다고 생각하고 있으며, 이를 검증해야 한다. 귀류법을 통해 수학적?으로 검증해보자.

n장의 카드묶음이 있을 때, 매 선택마다 임의의 카드묶음 2개를 골라 합쳐나갔을 때 나오는 각각의 비교횟수들이 있을 것이고 총 n-1번의 비교를 한다. 이 때 가장 작은 카드묶음 2개를 골라나갈 때 나오는 비교횟수들의 집합을

G = {g1, g2, g3, ..., g(n-1)}

이라 하고, 이 문제의 최적해의 비교횟수 집합을

O = {o1, o2, o3, ..., o(n-1)}

이라 해보자. 이 때 G가 이 문제의 최적해가 아니라면 sum(G) > sum(O)가 되야 한다. 그러나 실제로는 G가 가장 작은 카드묶음이므로 sum(G) < sum(O)가 되니 가정에 모순이다. 따라서 G는 이 문제의 최적해이다.

4. 끝나지 않은 문제

작은 애들부터 골라야 한다는 것을 증명했으니, 이젠 코드만 세우면 된다. 그러나 문제가 있다. 우선 오름차순으로 카드를 정렬하고 거기서 카드더미를 2개씩 골라 합쳐나갈 텐데, 이렇게 합쳐지는 카드를 그대로 두면 전체 카드더미가 오름차순 유지가 되지 않는다. 따라서 매번 고를때마다 다시 정렬을 해주거나 적절한 위치에 새로 만들어진 카드더미를 삽입해야 한다. 그러나 정렬의 시간복잡도는 O(nlogn)이고 삽입(리스트의 insert메소드)의 시간복잡도는 O(n)이므로, 정렬이 아니라 계속 합칠 때마다 적절한 위치에 삽입을 해준다고 해도 러프하게 생각하면 최악의 경우 O(n^2)만큼의 연산을 해야 하게 되며 n은 최대 100,000이므로 이 경우 시간초과가 날 것이다). 어떻게 해야 하는가..

5. 해결책은 heapq : 우선순위 큐

일반적인 큐는 FIFO를 만족하지만, 우선순위 큐는 그와 달리 데큐를 할 때 우선순위가 높은 애들이 먼저 나온다. 즉 이 문제에선 가장 작은 카드더미들에게 높은 우선순위가 있다고 하여 우선순위 큐를 쓸 수 있다. 파이썬에서 heapq의 pop의 시간복잡도는 O(1), push의 시간복잡도는 O(logn)으로 전체 시간복잡도는 최대 O(nlogn)정도가 되고 100,000이어도 160만번 정도의 연산만 하면 되므로 시간 내에 통과가 가능해진다. 따라서, 드디어 코드는 다음과 같다.

import heapq

N = int(input())

data = []

for _ in range(N):
    heapq.heappush(data, int(input()))

answer = 0

while len(data) != 1:
    min1 = heapq.heappop(data)
    min2 = heapq.heappop(data)
    heapq.heappush(data, min1 + min2)
    answer += (min1 + min2)

print(answer)

그리디 검증 관련 참고

1. http://v2everything.blogspot.com/2015/09/greedy-algorithm.html

2. https://gazelle-and-cs.tistory.com/59

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

0마리를 배치하는 것도 가능하고, 가로 세로로 붙지 않도록 배치해야 하므로 이론상 N마리까지 배치가능하다.

1. 브루트한 방법으로 풀이

직접 0 ~ N마리의 사자들을 하나하나 배치하는 방법이 있는데, 이 방법은 러프하게 생각하면 2^2n번 정도의 연산을 하게 될텐데 n은 100,000까지 주어질 수 있으므로 시간 내에 통과할 수 없을 것이다.

그렇다면 DP나 그리디를 통한 방법을 의심헤야 한다.

2. 우선 부분문제로 쪼갤 수 있는가?

쪼갤 수 있다. K마리(K <= N)의 사자를 배치한다고 할 때

1) 첫 사자를 첫째 줄 왼쪽 칸에 배치하는 경우

2) 첫 사자를 첫째 줄 오른쪽 칸에 배치하는 경우

3) 첫 사자를 첫째 줄에 배치하지 않는 경우

로 쪼갤 수 있다.

3. 그럼 중복되는 구조가 있는가? 있다면 DP로 풀이가 가능할 것이다.

중복되는 구조 역시 있다. N개의 행에 사자 K마리를 배치한다 할 때

첫 사자를 첫 줄 왼쪽에 배치할 땐 두 번째 사자를 다음 줄의 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄 오른쪽에 배치할 땐 두 번째 사자를 다음 줄의 왼쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄에 배치하지 않을 땐 두 번째 사자를 그 줄의 왼쪽 또는 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

정리하자면

f(N, K, left)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 왼쪽에 사자를 두는 경우

f(N, K, right)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 오른쪽에 사자를 두는 경우

f(N, K, no)를 N개의 행에 사자 K마리를 배치하는데 첫 줄에 사자를 두지 않는 경우라고 한다면

f(N, K, left) = f(N-1, K-1, right) + f(N-1, K-1, no)f(N, K, right) = f(N-1, K-1, left) + f(N-1, K-1, no)f(N, K, no) = f(N-1, K, left) + f(N-1, K, right) + f(N-1, K, no)이라는 관계를 구할 수 있고, 중복되는 케이스들을 관찰가능하다.

4. 점화식을 세워보자

사실 점화식은 위에서 이미 세웠다. dp[i][j][k]라는 배열을 만들어서 그대로 적용라면 되며, 최종적으론 dp[N][0] ~ dp[N][N]까지를 합치면 그것이 답이 될 것이다.그러나 문제가 있다. 저 식 그대로 DP배열을 만들어서 사용하자면 3차원 배열이 만들어지는데, N은 최대 10만이고 K도 N까지의 범위를 가지니 10만 X 10만 X 3 = 3백억의 크기를 갖는 배열이 만들어지고 이는 메모리 제한에 걸릴 것이다..여기서 막혔고, 많은 고민을 하다가 다른 분들이 푼 걸 참고하게 됐다..

위의 점화식은 "몇 마리의 사자를 배치하는가"에도 중점이 있는 점화식이며, 첫 줄의 왼쪽에 배치하는 경우와 오른쪽에 배치하는 경우 그리고 첫 줄에 배치를 하지 않는 경우라는 3가지 케이스로 쪼개어 경우의 수들을 관리한다. 그러나 X개의 행에서 K마리의 사자를 배치하는 여러 방법들이 있다고 할 때, 행의 수 X만 같다면 그 방법들 모두 한꺼번에 묶어서 첫 줄의 왼쪽/오른쪽에 배치하는 경우와 첫 줄에 배치하지 않는 경우라는 3가지 케이스로 분류할 수 있다. 행의 수만 같다면 마리 별로 배치하는 방법까진 고려하지 않아도 되는 것.

즉 dp[x]를 x개의 행(즉 2*x칸의 우리)에 사자들을 배치하는 방법이라 하면, dp[x] = dp[x][left] + dp[x][right] + dp[x][no]라는 3가지 케이스로 보는 게 더 편하다는 것임 

이렇게하면 점화식이 훨씬 쉬워진다.

dp[N][left] = dp[N-1][right] + dp[N-1][no]

dp[N][right] = dp[N-1][left] + dp[N-1][no]

dp[N][no] = dp[N-1][left] + dp[N-1][right] +dp[N-1][no]

N = int(input())

mod = 9901

dp = [[0, 0, 0] for _ in range(N + 1)]
dp[1] = [1, 1, 1]

for i in range(2, N + 1):
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod

print(sum(dp[N]) % mod)

느끼고, 배운 점

이 문제의 난이도가 실버1에 불과하단 걸 알고 현타가 왔다. 다른 사람들은 쉽게 생각하는 걸 나는 어렵게 생각했구나..라면서,, 

직관적으로 N=1일때의 배치방법, N=2일때의 배치방법들을 써가면서 규칙을 찾아 쉽게 푸는 방법도 있었다. 그래도 내가 한 방법이 잘못됐다고는 생각하지 않는다. 나만의 푸는 패턴을 만들어가며 연습하면서 감각을 길러가고, 실전에선 그 감각을 토대로 직관적으로(브루트하게 풀 수 있는지 없는지 따지고 그런 과정 없이) 풀 수 있을 거라고 생각한다..

배운 점은 글쎄..잘 모르겠다. 경험만이 살 길이란 생각이 들던 문제.

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

무식하게 풀어본다면 어떻게 풀 수 있을지 어림짐작을 하려고 했는데, 못 했다. 어떻게해서 풀 수 있을지는 구상이 되는데, 그 방법을 토대로 어떻게 어림짐작을 할 수 있을지를 모르겠었다. 직관적으로 떠오른 방법은 주어진 알파벳들을 자음과 모음들로 구분하고, 자음에서는 2개 이상을 고르는 모든 조합, 모음에서는 1개 이상을 고르는 모든 조합을 서로 매핑시켜서 암호를 만드는 것이었다. 일단 떠오르는 무식한 방법(비단 브루트포스 방식이 아니더라도)에 대한 어림짐작이 잘 안되면 일단 그 방법으로 풀어보는 것도 하나의 방법이라고 한다.

파이썬에서는 순열/조합에 관해서 쓸 수 있는 편리한 라이브러리가 있다.  이를 활용하기로 했으며, 코드는 다음과 같다.

from itertools import combinations
import sys

L, C = map(int, sys.stdin.readline().split())

# data[0] = 자음, data[1] = 모음
data = [list(map(str, sys.stdin.readline().split())), []]
password_list = []
# 자음 모음 분리 .
for ch in ['a', 'e', 'i', 'o', 'u']:
    if ch in data[0]:
        data[1].append(ch)
        data[0].remove(ch)

# 주어진 알파벳들로 암호를 만들 수 있을 경우는 자음이 2개, 모음이 1개 이상인 경우
if len(data[0]) >= 2 and len(data[1]) >= 1: 

    # i는 모음의 개수를 의미
    for i in range(1, len(data[1]) + 1):
        if L - i >= 2:
            vowels = list(combinations(data[1], i)) # 가능한 모든 모음의 조합
            consos = list(combinations(data[0], L - i)) # 그로부터 생기는 가능한 모든 자음의 조합
            for v in vowels:
                for c in consos:
                    # 모음의 조합과 자음의 조합들을 합쳐 비밀번호만들기
                    password = ''.join(sorted(list(v + c)))
                    password_list.append(password)

    # 비밀번호들 사전순 정렬
    password_list.sort()

    for i in password_list:
        print(i)

모음은 총 5개까지 고를 수 있는데, 주어지는 알파벳들이 중복되어 주어지는 것이 없다고 했으므로 모음은 0개 ~ 5개까지 있을 것이다. 따라서 자음 / 모음을 분리했을 때 모음이 1개 이상, 자음이 2개 이상 있어야지 암호를 만들 수 있으므로 이에 대한 예외처리를 해준다. 

combinations()의 파라미터로 첫 번째는 반복 가능한 것(배열처럼), 두 번째는 요소의 개수를 넣어주면 첫 번째로 받은 반복 가능한 객체에서 두 번째 파라미터로 받은 개수만큼의 조합을 튜플 형태들로 반환해준다. 주어진 알파벳들로 L글자의 암호를 만든다고 할 때, 모음의 개수를 정했다면 자음의 개수는 L - 모음의 개수이므로 이를 활용해 가능한 모음의 조합과 자음의 조합들을 만들어주고 이들을 합치고 정렬하여 알파벳 순서로 된 비밀번호를 만드는 식으로 코드를 짰다.

24번째 줄, if L - i >= 2를 처음엔 넣어주지 않아 틀렸다고 나왔다. 자음은 2개 이상, 모음이 1개 이상 있어도 모음의 개수에 따라 암호를 못 만들 수도 있는 상황이 있음을 간과한 것이었다. 예를 들어 자음이 3개, 모음이 3개 있을 때 4글자짜리 암호를 만들라고 했다고 하자. 자음이 2개 이상 모음은 1개 이상있는 상황이니 비밀번호를 아예 못 만드는 상황은 아니지만, 모음이 3개인 비밀번호는 만들 수 없다! 이 경우 자음은 1개만 써야 4글자짜리 비번을 만들 수 있는데, 문제의 조건 상 자음은 2개 이상 써야 하기 때문이다. 즉 이에 대한 예외처리를 해줘야했다. 

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

이 문제를 무식하게 모든 경우의 수를 따져서 풀려고 하면 어떻게 할 수 있을까? 각 열에서 하나의 스티커만 뽑을 수 있으므로 최대 n개의 스티커를 뽑을 수 있다. 즉 각 열에 대해 위의 스티커를 뽑던가, 아래의 스티커를 뽑던가, 안 뽑던가의 3가지 갈래가 있고 n열까지 있으니 3^n개의 조합들이 나오고, 여기서 변을 공유하는 스티커를 뽑은 케이스를 쳐내야한다. 즉 이 방법의 시간복잡도는 O(3^n)정도가 될 것이고 n은 문제에서 최대 100,000으로 주어진다 했으니 연산횟수는 천문학적인(?) 숫자가 된다. 주어진 시간제한 1초 내에 이 방법으로 문제를 푸는 것은 매우 힘들다..고 봐야 한다.

그럼 어떻게 접근할 수 있는가. 그리디하게 접근한다면 일단 각 열에서 무조건 스티커를 떼는데, 가장 높은 값의 스티커들만 떼가야 한다. 그러나 당연히 이는 불가능하다. 변을 공유하는 스티커를 뗄 수 없으니 1번째 열의 스티커를 떼면 그 다음 열에서 뗄 수 있는 스티커, 또 그 다음 열에서 뗄 수 있는 스티커가 정해진다. 이 방법은 최적의 답을 도출할 수 없다.

이번엔 dp를 의심해보자. 일단 이 문제는 부분 문제로 쪼갤 수 있다. 1번째 열부터 차례차례 스티커를 떼고 n번째 열의 스티커를 뗀다고 해보자. 물론 각 열의 스티커는 안 뗄 수도 있다. 이 때 정답은 가장 큰 점수를 얻는 스티커 조합이므로, 위쪽 스티커든 아래쪽 스티커든 간에 n번째 열의 스티커는 떼야 한다. 그렇다면 답은

마지막 스티커(n번째 열)을 위쪽을 뽑은 경우

마지막 스티커(n번째 열)을 아래쪽을 뽑은 경우

이 둘 중 하나다. 여기서 단순히 n번째 열 스티커를 위쪽을 뽑았다면, 이 점수를 n - 1번째 스티커를 아래쪽을 뽑은 경우에 나오는 값에 더해야 합니다. 라고 하면 안된다.  다음 예시를 보자

1 ~ 3열까지 스티커를 뽑았을 때 나오는 최대 점수는 몇인가? 라는 문제라면 1, 2열에서 뭘 뽑던 3열에서 스티커 하나를 뽑은 케이스가 정답이 된다. 3열에서 아래쪽을 뽑은 케이스를 알기 위해 2열에서 위쪽을 뽑은 케이스를 더한다면 이 때 구해지는 점수는 2 + 2 + 25 = 29가 된다. 그러나 3열에서 아래쪽을 뽑은 케이스의 최대값은 35다! 1열에서 10을, 2열에서 아무것도 안 뽑고 3열에서 25를 뽑은 케이스. 즉, n번째 열의 위쪽을 뽑은 경우 얻는 점수의 최대는

n - 1번째 스티커를 아래쪽을 뽑은 경우의 최대누적합

n - 2번째 스티커를 뽑은 경우(위, 아래 상관없음)의 최대누적합

이 둘 중 더 큰 값에 n번째 열의 위쪽스티커의 점수를 합한 것이다. dp[1][i]이 i번째 열에서 위쪽 스티커를 뽑은 경우의 최대누적합, dp[2][i]가 i번째 열에서 아래쪽 스티커를 뽑은 경우의 최대누적합이라 하면 점화식은 다음과 같이 얻어진다.

dp[1][n] = max(dp[2][n-1], max(dp[1][n-2], dp[2][n-2]))

dp[2][n] = max(dp[1][n-1], max(dp[1][n-2], dp[2][n-2]))

이걸 고대로 코드로 옮기면 된다.

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    sticker = [[0]]
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))

    dp = [[0 for i in range(n + 1)] for j in range(3)]
    dp[1][1] = sticker[1][1]
    dp[2][1] = sticker[2][1]

    for i in range(2, n + 1):
        dp[1][i] = max(dp[2][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[1][i]
        dp[2][i] = max(dp[1][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[2][i]

    print(max(dp[1][n], dp[2][n]))

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인 듯.