BOJ 2468번 - 안전 영역

[백준 온라인 저지 링크]

2468번: 안전 영역

한번만 더 틀리면 칠전팔기였을텐데... 조금 아쉽네요!

 

다른 분들 코드를 보니 한번의 탐색만으로 답을 구하는 분들이 많았는데, 저는 두 번의 탐색을 활용하는 코드를 작성했습니다.

테스트케이스로 주어진 배열과 함께 빗물의 높이가 3인 경우를 예로 들겠습니다.

첫 번째 BFS 탐색에서는 원본 배열을 탐색해 안전 여부를 판단하는 배열을 만들어냅니다.

두 번째 BFS 탐색에서는 이렇게 만들어진 안전 영역의 수를 세 줍니다.

 

다만 한 가지 조심할 점은 "비가 오지 않는 경우 (= 높이가 0일때)" 가 마지막 테스트케이스로 포함되어 있는 듯 합니다.

2

1 0

0 1

따라서 위와 같은 입력이 주어지면 최대 안전 영역은 2가 되어야 하니, 이것만 유의하면 기교 없이 깔끔하게 풀 수 있을 듯 합니다! 😁

[정답 코드 - Python]

from collections import deque

N = int(input())

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
area = []
visited = [[False] * N for _ in range(N)]
height = 0
safe_cnt = 0
max_safe_cnt = 0

for i in range(N):
    area.append(list(map(int, input().split())))

height = max(max(area))

# 첫 번째 탐색에서는 높이에 따라 가라앉는 여부가 담긴 boolean형 리스트를 만듭니다.
def bfs_make_sink(start_node, height):
    y, x = start_node
    q = deque()
    visited[y][x] = True
    q.append(start_node)
    while q:
        y, x = q.popleft()

        if area[y][x] > height:
            safe[y][x] = True

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                if visited[ny][nx] == False:
                    visited[ny][nx] = True
                    q.append((ny, nx))

# 두 번째 탐색에서는 위에서 얻은 리스트를 검사해 최대 안전 영역을 카운트합니다.
def bfs_get_safe(start_node):
    y, x = start_node
    q = deque()
    q.append(start_node)
    visited[y][x] = True
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                if visited[ny][nx] == False and safe[ny][nx] == True:
                    visited[ny][nx] = True
                    q.append((ny, nx))


for i in range(0, height + 1):
    safe_cnt = 0
    safe = [[False] * N for _ in range(N)]
    bfs_make_sink((0, 0), i)
    visited = [[False] * N for _ in range(N)]
    for row in range(N):
        for col in range(N):
            if visited[row][col] == False and safe[row][col] == True:
                bfs_get_safe((row, col))
                safe_cnt += 1

    if safe_cnt >= max_safe_cnt:
        max_safe_cnt = safe_cnt

    visited = [[False] * N for _ in range(N)]

print(max_safe_cnt)

풀이 코드가 이렇게 보니 꽤 기네요...