[백준] 2468번 | 안전영역

풀기 전 생각 정리

1) 최소 높이와 최대 높이를 구해, 해당 범위만 bfs 활용하자
2) 높이, column, row 3중 for문에 의해 시간 초과는 나지 않는지
계산 후 시간 초과가 나지 않는 것으로 판명

코드

import sys
from collections import deque
from copy import deepcopy

def bfs(arr, number, n, col, row):
    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]
    que = deque()
    que.append((col, row))
    arr[col][row] = number

    while que:
        x, y = que.popleft()
        for i in range(4):
            t_x = x + dx[i]
            t_y = y + dy[i]
            if 0 <= t_x < n and 0 <= t_y < n and arr[t_x][t_y] > number:
                que.append((t_x, t_y))
                arr[t_x][t_y] = number
    return arr

def execut(arr, number, n):
    temp_arr = deepcopy(arr)
    count = 0
    for i in range(n):
        for j in range(n):
            if temp_arr[i][j] > number:
                temp_arr = bfs(temp_arr, number, n, i, j)
                count += 1
    return count

n = int(sys.stdin.readline())
arr = list()
result = list()
for i in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

min_value = 101
max_value = 0
for i in range(n):
    t_max = max(arr[i])
    t_min = min(arr[i])
    if t_max > max_value:
        max_value = t_max
    if t_min < min_value:
        min_value = t_min

for i in range(min_value):
    result.append(1)
for number in range(min_value, max_value):
    result.append(execut(arr, number, n))

print(max(result))

리뷰

• 배열을 계속 활용하기 위해 deepcopy를 활용했지만, visited를 만들어 활용해도 괜찮을 것 같다.
  (Visited를 n*n으로 만들어 방문 했던 곳은 number로 바꾸는 것이 아닌 1로 올려 다음에 못 들어오게 만드는 방법)
• 최소, 최대값을 구하는 부분을 for문으로 구현했는데 다른 분들은 아래 방법을 이용했다.

graph_min = min(map(min, graph))    # min_height
graph_max = max(map(max, graph))    # max_height