[백준]2468- 안전지역 문제 풀이(파이썬,Python)

문제

2468번: 안전 영역

 

들어가며

문제를 잘 읽어봐야 한다.

빗물이 차오르는 높이는 딱히 정해져있지 않고, 그 수 많은 빗물이 차오르는 높이 중에서 어느 높이일 때, 만들어지는 안전 구역 개수의 최대값이다.

즉, 높이는 0 ~ 최대 안전구역 높이 라고 말할 수 있다.

또한 구역의 개수라고 하면 바로 감이 오시는 사람이 있을 것이다.

 

bfs 또는 dfs 문제이다.

 

코드

from collections import deque

n = int(input())
directions = { (0, 1), (0, -1), (1, 0), (-1, 0) }
visited = [[False] * n for _ in range(n)]
arr = []
arr_max = 0

for _ in range(n):
    numbers = list(map(int, input().split()))
    arr.append(numbers)
    arr_max = max(arr_max, max(numbers))


def bfs(start_x,start_y, goal):
    global n, directions, visited
    queue = deque()
    queue.append((start_x,start_y))
    visited[start_x][start_y] = True
    while len(queue) != 0:
        current_x, current_y  = queue.popleft()

        for dir in directions:
            next_x = dir[0] + current_x
            next_y = dir[1] + current_y

            if next_x < 0 or next_y <0 or next_x >= n or next_y >= n:
                continue

            if visited[next_x][next_y]:
                continue

            if arr[next_x][next_y] <= goal:
                continue
            queue.append((next_x,next_y))
            visited[next_x][next_y] = True
    return 1

ret = 0
for threshold in range(arr_max):
    result = 0
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and arr[i][j] > threshold:
                result += bfs(i, j, threshold)
    ret = max(result, ret)

print(ret)

풀이법

bfs로 풀었다.

(사실 dfs가 더 적절해 보인다)

 

 

아무튼 이를 설명하자면 다음과 같다.

from collections import deque

n = int(input())
directions = { (0, 1), (0, -1), (1, 0), (-1, 0) }
visited = [[False] * n for _ in range(n)]
arr = []
arr_max = 0

for _ in range(n):
    numbers = list(map(int, input().split()))
    arr.append(numbers)
    arr_max = max(arr_max, max(numbers))

 

이 부분은 bfs 탐색을 위한 초기값 및 문제가 제시하는 입력값을 셋팅하는 단계이다.

directions의 용도는 상하좌우를 확인하기 위해 사용되며 후술할 것이다.

또한, 현재 방문했는지 확인하기 위해 visited 2차원 리스트를 사용한다.

arr은 문제에서 알려주는 전체 배열의 값이다.

arr_max는 bfs 탐색에 제한을 두기 위해 나온 값 중에서 최대값을 기록해둔다. 이 또한 후술할 것이다.

 

def bfs(start_x,start_y, goal):
    global n, directions, visited
    queue = deque()
    queue.append((start_x,start_y))
    visited[start_x][start_y] = True
    while len(queue) != 0:
        current_x, current_y  = queue.popleft()

        for dir in directions:
            next_x = dir[0] + current_x
            next_y = dir[1] + current_y

            if next_x < 0 or next_y <0 or next_x >= n or next_y >= n:
                continue

            if visited[next_x][next_y]:
                continue

            if arr[next_x][next_y] <= goal:
                continue
            queue.append((next_x,next_y))
            visited[next_x][next_y] = True
    return 1

 

전형적인 bfs 코드이다.

반복문 형식으로 풀었다. 그렇기에 queue를 사용했다.

여기서 directions 딕셔너리의 사용처가 들어난다.

현재 좌표에서 상하좌우의 좌표를 구하기 위해 사용된다. (next_x, next_y 계산)

next_x, next_y를 구한 이후엔 검증에 들어간다.

1. 전체 배열을 넘어섰는지

2. 이미 방문한 건지

3. 물의 높이보다 작은지 (침수된 곳은 제외해야 하므로)

 

마지막으로 bfs에 들어갔다는 뜻은 반드시 한 구역이 있다는 것으로 무조건 return 1이 된다.

 

왜 반드시 한 구역이 있을까??

그건 바로 밑의 bfs 호출 부분을 보면 알 수가 있다.

ret = 0
for threshold in range(arr_max):
    result = 0
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and arr[i][j] > threshold:
                result += bfs(i, j, threshold)
    ret = max(result, ret)

print(ret)

 

먼저, 이 전에 지역의 높이들을 입력받을 때, 가장 최대값을 arr_max에 저장해두었다.

따라서 0 ~ arr_max까지 threshold라고 정의하고 반복문을 진행한다.

각 물 높이마다 새로 계산해야 하기 때문에, visited를 재정의한다.

그 이후, 구역을 구하는 작업을 시작한다. 배열의 모든 좌표에서 시작한다.

이때, 이미 방문했거나, threshold보다 작다면, bfs를 실행할 필요가 없으므로 제외한다.

이렇기에 위에서 무조건 return 1 을 진행한다.

마지막으로 이전 높이에서 구한 구역의 개수와 비교하여 큰 값을 결과에 넣어두고 출력한다.