[Baekjoon/Python] 2468. 안전 영역 (BFS)

---

문제

N×N 크기의 지역이 주어지고, 각 칸에는 높이가 있다.
비가 일정 높이만큼 내리면 그 높이 이하의 모든 지역은 물에 잠긴다.

물에 잠기지 않은 칸들끼리 상하좌우로 연결되어 있다면 하나의 안전 영역으로 본다.
비의 높이를 바꿔가며 안전 영역의 최대 개수를 구하는 문제이다.

---

📚 문제 분석

1. 핵심은 “여러 번 탐색해야 하는 문제”이다

비의 높이가 하나로 고정되어 있지 않다.
따라서 한 번 BFS/DFS로 끝나는 문제가 아니라,
비의 높이를 바꿔가며 매번 안전 영역 개수를 다시 계산해야 한다.

2. 안전 영역은 연결 요소 개수 문제이다

잠기지 않은 칸들을 기준으로 보면,
결국 상하좌우로 연결된 덩어리 개수를 세는 문제이다.

→ BFS 또는 DFS로 해결 가능

3. 탐색 기준

• graph[i][j] > rain → 잠기지 않은 칸 (안전 영역)
• 이 조건을 만족하는 칸들끼리 연결된 영역 개수 세기

4. 비의 범위

비는 0 ~ (최대 높이-1)까지 확인하면 충분하다.

• rain = 0 → 비가 안 온 경우
• rain >= max_height → 전부 잠김 → 의미 없음

---

💻 나의 최종 코드 (정석 코드)

from collections import deque

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

maximum = max(max(row) for row in graph)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def get_secure_zone(rain):
    secure_num = 0
    visited = [[False] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if visited[i][j] or graph[i][j] <= rain:
                continue

            queue = deque([(i, j)])
            visited[i][j] = True

            while queue:
                x, y = queue.popleft()

                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]

                    if 0 <= nx < N and 0 <= ny < N:
                        if not visited[nx][ny] and graph[nx][ny] > rain:
                            visited[nx][ny] = True
                            queue.append((nx, ny))

            secure_num += 1

    return secure_num

answer = 0

for rain in range(maximum):
    answer = max(answer, get_secure_zone(rain))

print(answer)

---

🔥 시행착오했던 풀이

1. 그래프를 직접 변경하는 방식으로 접근
처음에는 매번 그래프를 복사해서 BFS 중 방문한 칸을 0으로 바꾸는 방식으로 구현했다.

tgraph[tx][ty] = 0

그래서 매 강수량마다 그래프를 복사해서 사용하려고 했다.

get_secure_zone(copy.deepcopy(graph), rain)

이 방식 자체는 동작은 가능하다.
다만, 매번 깊은복사를 해야하기때문에 무거워질수 있어 visited 배열로 따로 방문처리하는 편이 낫다. 이 방법은 3번에서 다시 다루겠다.

2. 2차원 리스트 복사 문제 발생

처음에는 deepcopy 대신 아래처럼도 시도했다가 실패했다.

graph[:]

1차원 리스트였다면 깊은 복사가 되었겠지만, 2차원 리스트의 경우 깊은복사가 안된다.

• 바깥 리스트만 복사됨
• 내부 리스트는 그대로 공유됨

그래서 BFS 중에 값을 바꾸면
원본 graph까지 같이 바뀌는 문제가 발생했다.

이 때문에 다음 강수량 계산에서
이미 변경된 그래프를 사용하게 되어 오답이 발생했다.

3. 해결 방법

• copy.deepcopy(graph) 사용 → 완전한 깊은 복사
• 또는 [row[:] for row in graph] 사용

하지만 이 문제에서는 더 좋은 방법이 있다.

→ 그래프를 건드리지 않고 visited 배열을 사용하는 것

이렇게 하면 복사 자체가 필요 없어지고,
코드도 훨씬 깔끔해진다.

• graph[i][j]는 높이 정보
• visited[i][j]는 방문 여부
  이렇게 역할이 나뉘어 있어서 코드가 더 명확하다.

한번만 검사할때는 visited 없이 그래프를 직접 바꾸는게 더 간단하겠지만,
여러 조건을 반복해서 검사해야 할 때는 그래프를 직접 바꾸는 방식은 불편해질 수 있다.

4. 비가 안 오는 경우를 따로 처리했던 점

• 0<= rain < min : 안전지대 항상 1개
• min <= rain < max : 안전지대 1개 이상

처음에는 위의 조건대로 0<= rain < min 범위에서는 안전지대가 항상 1개이기 때문에 이 범위에 대해서 탐색할 필요가 없다고 생각했다.
그래서 result 리스트에 강수량별 안전지대 개수를 저장해놓고, 마지막에 max(result)를 정답으로 출력할 생각이었다.

result = [1]

로 0<= rain < min범위의 안전지대 값(1)으로 초기화해두고,
min <= rain < max에 대해 안전지대 개수를 구해 result에 추가하는 방식이다.

하지만, 이 문제의 시간복잡도는 O(높이 범위 × N²) 으로,
0<= rain < min를 포함하나 안하나 시간복잡도에 큰 영향을 주지 않는다.
최악의 경우, 100 × (100 × 100) = 1,000,000번 정도 이다.

물론 조금이라도 시간을 줄이고싶다면, 최적화하는게 좋겠지만, 세세하게까지 다루다 실수해버릴수도 있기 때문에 휴먼에러와 코드단순화를 생각한다면 좀 더 단순하게 가는게 좋아보인다.

---

🤔 느낀점

문제의 큰 틀, 즉 핵심 풀이 아이디어는는 잘 파악했으나, 이를 구현하는 과정에서 오래걸린 것이 아쉽다.
사실 큰틀만 놓고보면 '단지 번호 붙이기' 같은 연결요소개수 구하기를 * n번 반복하는 것 뿐이다. 근데 왜이렇게 오래걸렸을까...
너무 복잡하게, 사소한것까지 최적화하려고 해서 그런것 같다. 시간복잡도를 고려해서 필요없는 최적화는 버리고 단순하게 가는것도 중요하겠다.

---

✏️ 배운점

1. 연결 요소 문제로 변환하는 사고가 중요하다

처음에는 단순히 “잠기는 영역”에 집중했지만,
실제 문제는 잠기지 않은 영역의 개수를 구하는 문제였다.

→ BFS/DFS 문제로 바꿔 생각하는 것이 핵심

2. 그래프를 직접 바꿀지, visited를 쓸지 먼저 결정해야 한다

• 그래프 직접 변경 → 구현은 쉽지만 복사 문제 발생
• visited 사용 → 조금 더 구조적이고 안정적

특히 이 문제처럼 여러 번 탐색해야 할 때는 visited 방식이 훨씬 유리하다.
상황에 따라 판단하자.

3. 2차원 리스트 복사 개념은 반드시 정확히 알아야 한다

• graph[:] → 얕은 복사 (실수 포인트)
• [row[:] for row in graph] → 2차원 복사 가능
• copy.deepcopy(graph) → 완전한 깊은 복사

이 차이를 모르고 BFS/DFS 문제를 풀면
디버깅이 매우 어려워진다.

4. 모든 경우를 하나의 흐름으로 처리하는 것이 더 안전하다

예외를 따로 두기보다

for rain in range(maximum):

처럼 통일된 구조로 처리하면 코드가 단순해지고 실수도 줄어든다.(시간복잡도에 큰 영향을 미치지 않는 경우)

---