작심큰일 챌린지 - Day 2. 안전 영역 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

2일째 문제 풀이가 시작 됐다. 오늘은 오후에 일정이 있었어서 저녁에서야 문제를 풀 수 있었다.

 

작심큰일 챌린지같은 경우, 챌린지 기한 내에서 문제를 제출하기만 하면 된다.

 

하루 1문제씩 꾸준히 문제풀이하는 습관을 형성한다는 목표와 성취감을 느끼기 위한 과정이라 정답여부도 중요하지 않다.

 

하지만 대충 문제를 풀고 해설을 보면 의미가 없으니 최선을 다해서 문제를 푸는 것이 핵심이 될 것 같다.

---

Day 2. 안전 영역

오늘의 문제는 백준 프로그래밍 2468번 문제다.

문제

문제 펼쳐보기/접기

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

 

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

 

 

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

 

 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

• 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다.
• N은 2 이상 100 이하의 정수이다.
• 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다.
• 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다.
• 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력 1

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1

5

예제 입력 2

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

예제 출력 2

6

---

풀이 과정

문제를 풀기 전에 먼저 어떤 식으로 코드를 구성할지 작성해 보았다.

 

1. 입력값 N을 기반으로 이후에 입력받는 N행의 2차원 배열을 생성
2. 각 행의 정보를 입력받고, 행의 정보를 배열에 추가
    a. 배열에 추가할 때 모든 경우의 수를 계산하기 위한 최대 물의 높이를 계산
3. 1부터 최대 물의 높이까지의 경우의 수를 순회
    a. 순회할 때 영역을 계산

 

DFS vs. BFS

상/하/좌/우 각 인접 영역에 따라 붙어있는지 확인하는 과정에서 생성된 배열(또는 그래프)을 "효율적으로 탐색"해야 한다.

 

대표적인 방법인 DFS(Dept-Frist-Search)와 BFS(Breadth-First-Search) 중 어느쪽이 더 해당 문제에 효율적인지가 고민이 됐다.

 

이전에 BFS와 DFS의 차이점을 공부하고 요약한 내용을 다시 찾아봤다.

 

 

추가로 좀 더 찾아봤는데, 파이썬의 경우 BFS가 더 무난한 선택지가 된다고 한다.

 

대표적인 이유로 몇 가지가 있다.

 

파이썬에서 DFS를 재귀로 구현할 때, 연결된 지역이나 미로, 영역이 매우 크면 재귀 호출이 너무 깊어져 RecursionError(재귀 한계 초과 에러)가 자주 발생하는데, BFS는 큐를 사용해서 이런 문제가 없다.

 

또한, BFS는 인접한 칸(동일 거리/깊이)을 모두 먼저 탐색하여 모든 영역을 공평하게 처리한다.

 

즉, DFS는 구현이 쉽고 재귀가 단순하지만 파이썬의 재귀 한계 덕분에 실전에서 불안정하므로 BFS를 쓰는 것이 좋다. 단, 큐를 "잘" 써야 오류 없이 동작한다.

 

코드 구현

 

먼저 BFS 함수를 정의했다.

 

from collections import deque
# . . .

# BFS 함수 정의
def bfs(x, y, height, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    # 상하좌우 방향
    directions = [(-1,0),(1,0),(0,-1),(0,1)]

    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            # 범위 내, 방문 전, 물에 잠기지 않은 지역
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and graph[nx][ny] > height:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

 

기본적인 BFS 함수 틀을 유지하면서 물 높이(height)를 고려할 수 있도록 구성했다.

 

로직 자체가 크게 변경되는 부분은 없고, 각 칸의 높이(graph[nx][ny])가 현재 물 높이(height)보다 커서 물에 잠기지 않는 경우만 방문이 가능하도록 조건을 추가했다.

 

이후에는 앞서 정리했던 로직들을 모듈 느낌으로 하나씩 합쳤다.

 

from collections import deque
import sys

input = sys.stdin.readline

N = int(input())
graph = []
max_height = 0

for _ in range(N):
    row_data = list(map(int, input().strip().split()))
    graph.append(row_data)
    max_in_row = max(row_data)
    if max_in_row > max_height:
        max_height = max_in_row

# BFS 함수 정의
def bfs(x, y, height, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    # 상하좌우 방향
    directions = [(-1,0),(1,0),(0,-1),(0,1)]

    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            # 범위 내, 방문 전, 물에 잠기지 않은 지역
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and graph[nx][ny] > height:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

max_safe_area = 0

for height in range(1, max_height + 1):
    # 매 height마다 방문 기록 초기화
    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 graph[i][j] > height:
                bfs(i, j, height, visited)
                count += 1
    
    if count > max_safe_area:
        max_safe_area = count

print(max_safe_area)

 

max_safe_area를 별도로 기록하여 bfs 기준으로 count가 높다면 덮어씌우는 방식으로 적용했다.

 

이를 통해 "안전 영역의 최대 개수가 보장되는 물의 높이"가 아닌, "안전 영역의 최대 개수"로 표현할 수 있었다.

---

개선점

 

bfs를 하나도 안 보고 작성할 수 있다면 참 좋겠지만... 아직 그 정도 수준은 못 되는 것 같다.

 

다만 문제 자체가 명확해서 그런지 시니어 해설과 상당히 유사했다.

 

해설의 핵심 포인트는 다음과 같았다.

 

- 완전탐색 + 아몰라 2차원 배열이면 BFS/DFS 떠올릴 수 있겠어?
- 그래서 뭐 쓸껀데?
- 이론은 알 수 있지. 그래서 구현은?

 

 

내가 생각했던 부분들, 그리고 구현에 대해 아쉬워했던 부분들이 정확히 짚어져 있어서 뿌듯했다.

 

해설에서 제시한 코드는 DFS 기반이었는데, 직관적이고 빨리 구현할 수 있기 때문에 채택했다고 설명했다. 

 

이론적인 부분에서는 납득이 안 가는 부분이나 어려웠던 부분이 없었기 때문에 마음이 편안했지만, 구현하는 과정까지 생각해야 할 부분들이나 구현 자체가 꽤 시간이 걸려서 더 많은 BFS/DFS 기반 문제들을 풀어봐야겠다는 생각을 했다.

 

+ 추가 수정

코드 제출 전까지 몰랐는데, 한 가지 놓친 부분이 있었다.

 

for height in range(1, max_height + 1):

 

해당 코드인데, 이건 문제 해석에서 내가 오류를 범했기 때문이었다.

 

높이는 1이상 100 이하의 정수이다.

 

라는 조건을 읽고 height를 1부터 설정했는데, 이는 배열 내에 기입하는 "건물들의 높이"를 말한 것이었다.

 

즉, 물 높이는 0부터 시작할 수 있다.

 

"아무 지역도 물에 잠기지 않을 수도 있다."

 

문제 하단 노트 영역에도 이 부분이 적혀 있었다.

 

따라서 

 

for height in range(0, max_height + 1):

 

으로 수정하는 것이 맞다.

 

해설에서도 해당 코드는 위와 같이 작성 되었는데, 내가 당연히 맞다고 생각하고 넘어갔어 버렸다.

 

 

다음 번엔 문제를 꼼꼼히 읽기를...