TIL) 2468 안전지역

🍨 dfs 얼음만들기 확장판

나동빈 코딩테스트 책에서 풀었던 얼음만들기와 매우 유사한 문제이다. 다만 조건이 더 까다로워졌고 더 다양한 경우를 구해야해서 구현이 어려워졌다.

💡 아이디어

• 비는 0부터 건물의 최대높이까지 올 수 있다. 각각의 경우에 대해서 안전지역의 개수를 구한 후 개수의 최소값을 구한다.
• 비가 오는 양을 구해서 각각에 대해 T/F 이차원 배열을 만들어줘야한다.
• dfs를 이용해서 현재 위치를 기준으로 상하좌우를 확인해줘야한다.

from sys import *
setrecursionlimit(10 ** 6)

N = int(input())

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

# 최대값 구하기
max_num = 0
for h_list in graph:
    max_num = max(max_num, max(h_list))
# print(max_num)



def dfs(x, y):
    if x < 0 or x >= N or y <0 or y >= N:
        return False
    if tf_graph[x][y] == True:
        tf_graph[x][y] = False
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False


answer = 0
# 엄청난 사실 : [[0]*N]*N 으로 선언하면 모든 리스트가 연결되서 같이 변형된다. deepcopy()해주거나 따로 생성해줘야한다.
tf_graph = [[0]*N for i in range(N)]
# T/F 그래프 만들기
for n in range(0, max_num+1):
    result = 0
    for i in range(N):
        for j in range(N):
            if graph[i][j] > n:
                tf_graph[i][j] = True
            else:
                tf_graph[i][j] = False
    # print(tf_graph)
    for i in range(N):
    # dfs 검사하기
        for j in range(N):
            if dfs(i, j) == True:
                result += 1
    answer = max(answer,result)

print(answer)