백준 2468번 안전 영역 문제풀이 Python

🌊 백준 2468번 - 안전 영역

🔗 문제 링크 바로 가기

---

📌 문제 요약

장마철에 많은 비가 내리면, 일정 높이 이하의 지역이 물에 잠기게 됩니다.
이때, 물에 잠기지 않고 연결된 지역(상하좌우)은 하나의 안전 영역으로 봅니다.
비의 높이를 0부터 100까지 변화시키며 안전한 영역의 개수를 세고, 그중 최댓값을 구하는 것이 목적입니다.

---

🧠 핵심 아이디어

• 2차원 배열로 지형을 받고
• 비의 높이를 0~100까지 하나하나 바꿔가며 시뮬레이션
• DFS(깊이 우선 탐색)를 통해 물에 잠기지 않은 지역을 하나의 안전 영역으로 탐색
• DFS는 스택을 사용해 직접 구현
• 안전 영역 개수의 최댓값을 저장하여 마지막에 출력

---

✅ 전체 코드

N = int(input())  # 지도의 크기
arr = []
for i in range(N):
    tmp = list(map(int, input().split()))
    arr.append(tmp)

max_cnt = -1  # 안전 영역의 최대 개수

# 강수량 k를 0~100까지 시뮬레이션
for k in range(101):
    st = []  # DFS를 위한 스택
    cnt = 0  # 이번 강수량에서의 안전 영역 수
    check = [[0 for _ in range(N)] for _ in range(N)]  # 방문 확인 배열

    for i in range(N):
        for j in range(N):
            # 아직 방문 안 했고, 잠기지 않은 지역이면 DFS 시작
            if check[i][j] == 0 and arr[i][j] > k:
                st.append([i, j])
                check[i][j] = 1

                # DFS 시작
                while len(st) != 0:
                    x, y = st.pop()

                    # 상
                    if x - 1 >= 0 and check[x-1][y] == 0 and arr[x-1][y] > k:
                        st.append([x-1, y])
                        check[x-1][y] = 1

                    # 하
                    if x + 1 < N and check[x+1][y] == 0 and arr[x+1][y] > k:
                        st.append([x+1, y])
                        check[x+1][y] = 1

                    # 좌
                    if y - 1 >= 0 and check[x][y-1] == 0 and arr[x][y-1] > k:
                        st.append([x, y-1])
                        check[x][y-1] = 1

                    # 우
                    if y + 1 < N and check[x][y+1] == 0 and arr[x][y+1] > k:
                        st.append([x, y+1])
                        check[x][y+1] = 1

                cnt += 1  # 안전 영역 하나 완료

    # 이번 강수량에서의 최대값 갱신
    if cnt > max_cnt:
        max_cnt = cnt

# 최종 최대 안전 영역 수 출력
print(max_cnt)

---

🔍 코드 설명 (섹션별 해설)

📦 입력 받기

N = int(input())
arr = []
for i in range(N):
    tmp = list(map(int, input().split()))
    arr.append(tmp)

• N은 지역의 크기입니다.
• 각 줄마다 공백으로 나뉜 숫자를 받아서 arr이라는 2차원 리스트에 저장합니다.
• 이 배열은 지역의 고도를 나타냅니다.

🧮 안전 영역 최댓값 변수 초기화

max_cnt = -1

• 가장 많은 안전 영역의 개수를 저장하기 위한 변수입니다.
• 비교를 위해 음수부터 시작합니다.

🌧 비의 높이를 0부터 100까지 바꾸며 시뮬레이션

for k in range(101):

• 비가 0에서 100까지 올 수 있으므로 그만큼 반복합니다.
• k는 이번 시뮬레이션에서의 비 높이입니다.

🔍 시뮬레이션 준비: DFS를 위한 스택과 방문 체크 배열

st = []
cnt = 0
check = [[0 for _ in range(N)] for _ in range(N)]

• st: DFS용 스택
• cnt: 이번 비의 높이에서 안전 영역 몇 개인지 저장
• check: 방문했는지 확인하는 배열 (0이면 미방문)

🧭 DFS로 안전 영역 탐색 시작

for i in range(N):
    for j in range(N):
        if check[i][j] == 0 and arr[i][j] > k:

• 아직 방문하지 않았고, 잠기지 않은 곳(arr[i][j] > k)이면 DFS 시작합니다.

✅ DFS 시작 지점 저장 + 방문 처리

st.append([i, j])
check[i][j] = 1

• 스택에 시작점을 넣고
• check 배열로 방문 표시합니다.

🔁 DFS 탐색 - 상하좌우로 뻗어 나감

while len(st) != 0:
    x, y = st.pop()

• DFS는 스택이 빌 때까지 계속 탐색합니다.
• 현재 좌표를 꺼냅니다.

🔼 상 방향 이동

if x - 1 >= 0 and check[x-1][y] == 0 and arr[x-1][y] > k:
    st.append([x-1, y])
    check[x-1][y] = 1

• 배열 범위 안이고, 아직 방문 안했고, 안 잠겼으면 → DFS 계속합니다.

🔽 하, ◀ 좌, ▶ 우 방향도 똑같이 작성됨

• (하단, 좌측, 우측 코드가 모두 포함되어 있습니다.)

✅ DFS 종료 후 안전 영역 1개 카운트

cnt += 1

• 하나의 연결된 구역이 끝났다는 뜻이므로 안전 영역 1개 추가합니다.

⬆️ 최대값 갱신

if cnt > max_cnt:
    max_cnt = cnt

• 현재까지의 최대 안전 영역 수를 갱신합니다.

🖨 결과 출력

print(max_cnt)

• 시뮬레이션 결과 중 가장 많은 안전 영역 수를 출력합니다.

---

🔧 개선점 및 리팩토링 제안

최초 코드는 전혀 문제가 없지만, 다음과 같은 점에서 개선될 여지가 있습니다.

✅ 개선점 1: 재귀 DFS로 구현 가능

현재 DFS는 스택을 직접 구현했지만, Python의 재귀 호출을 이용해 DFS를 좀 더 간결하게 표현할 수 있습니다.

💡 왜 좋은가?

• 코드가 간단하고 가독성이 높습니다.
• DFS의 구조를 함수 하나로 추상화시킬 수 있습니다.

✅ 개선점 2: 방향 배열 활용

반복되는 상하좌우 코드 블록을 배열로 묶으면 반복문 하나로 처리 가능합니다.

💡 왜 좋은가?

• 코드 중복 제거
• 유지보수가 쉬워집니다.

✅ 개선점 3: 강수량 최대값까지만 시뮬레이션

비는 0~100까지 도는 대신, 입력된 지형의 최대 높이까지만 검사하면 충분합니다.

💡 왜 좋은가?

• 불필요한 연산 제거 → 시간 최적화
• 최악의 경우 101번 → 80번 미만으로 줄어듭니다.

---

✨ 개선 코드 1: 재귀 DFS + 방향배열 + 최댓값만 도는 최적화 버전

import sys
sys.setrecursionlimit(10000)

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

# 지형에서 가장 높은 곳까지만 시뮬레이션
max_height = max(map(max, arr))
max_safe = 0

# 상하좌우 방향벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, h, visited):
    visited[x][y] = True
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < N and 0 <= ny < N:
            if not visited[nx][ny] and arr[nx][ny] > h:
                dfs(nx, ny, h, visited)

for rain in range(0, max_height + 1):
    visited = [[False]*N for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and arr[i][j] > rain:
                dfs(i, j, rain, visited)
                count += 1
    max_safe = max(max_safe, count)

print(max_safe)

---

🔍 개선 코드 설명

📌 sys.setrecursionlimit(10000)

• Python의 기본 재귀 깊이는 1000입니다.
• 최대 100 x 100 크기의 지도에서 DFS가 깊게 들어갈 수 있으므로 예외 방지합니다.

📌 max(map(max, arr))

• 입력된 지형에서 가장 높은 지점만 찾아서
• 불필요하게 100번까지 돌지 않도록 최적화합니다.

📌 방향 배열 dx, dy

• 상하좌우를 인덱스 하나로 간결하게 반복 처리합니다.
• 확장성과 유지보수에 탁월합니다.

📌 DFS 함수

def dfs(x, y, h, visited):
    visited[x][y] = True
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < N and 0 <= ny < N:
            if not visited[nx][ny] and arr[nx][ny] > h:
                dfs(nx, ny, h, visited)

• 현재 위치 (x, y)에서 물에 잠기지 않은 곳만 탐색합니다.
• 재귀적으로 연결된 모든 안전 영역을 방문 처리합니다.

📊 성능 비교 (대략적)

구현 방식	코드 길이	가독성	확장성	시간 효율
스택 DFS	중간	보통	중간	O(N²)
재귀 DFS + 개선	짧음	높음	높음	개선됨

---

🌟 개선 코드 2: BFS 방식 (큐 사용)

from collections import deque

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
max_height = max(map(max, arr))
max_safe = 0

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

def bfs(x, y, h, visited):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and arr[nx][ny] > h:
                    visited[nx][ny] = True
                    q.append((nx, ny))

for rain in range(max_height + 1):
    visited = [[False]*N for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and arr[i][j] > rain:
                bfs(i, j, rain, visited)
                count += 1
    max_safe = max(max_safe, count)

print(max_safe)

---

📌 어떤 걸 써야 할까?

상황	추천 방식
단순 구현 & 빠르게 작성	스택 DFS (최초 코드)
가독성 좋고 깔끔하게	재귀 DFS
재귀를 못 쓰거나 깊이가 걱정되면	큐 BFS
실무/대회에서 신뢰 높은 방식	BFS or 스택 DFS

---

🧾 마무리 정리

• 처음에는 스택으로 DFS를 구현했지만, 이후 방향 배열, 재귀 함수, 입력 최적화 등 여러 개선을 통해 코드를 정리할 수 있습니다.
• 알고리즘 구현의 포인트는 "내가 이해 가능한 수준에서 점진적으로 리팩토링하는 것"입니다.
• 덩어리를 찾는 문제는 DFS/BFS + 시뮬레이션 조합이 핵심이므로, 여러 방식으로 연습해 보는 것이 좋습니다.