[백준] 2468번 : 안전 영역[Python]

문제 : https://www.acmicpc.net/problem/2468

2468번: 안전 영역

풀이 :

1. 1부터 100이하의 높이마다 각 안전 영역의 개수를 세주어야 하므로 find_safety함수를 만들기로 함

find_safety(h) 함수는

안전 지역 -> 1

물에 잠기는 지역 -> 0

으로 그래프를 변경해주는 함수

2. 이후 높이를 1씩 증가시켜가면서 bfs 진행을 통해 높이에 따른 안전영역의 개수를 파악

 

+ 추가적으로 백준 14502 연구소 문제도 이와 비슷하니 한번 풀어보는 것을 추천 드립니다.

14502 연구소 : https://www.acmicpc.net/problem/14502

14502번: 연구소

 

코드 :

from collections import deque
import copy
N = int(input())

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

dx = [0,0,-1,1]
dy = [1,-1,0,0]

answer = []

def find_safety(h):     # 높이가 커질수록 안전지역이 달라지므로 이를 확인하기 위한 함수
    visited = [[False]*N for _ in range(N)]     
    safety_graph = copy.deepcopy(graph)     # graph 깊은 복사
    for i in range(N):
        for j in range(N):
            if safety_graph[i][j] > h and not visited[i][j]:
                safety_graph[i][j] = 1      # 잠기지 않은 지역
                visited[i][j] = True
            elif safety_graph[i][j] <= h and not visited[i][j]:
                safety_graph[i][j] = 0      # 잠긴 지역
                visited[i][j] = True
    return safety_graph


def bfs(y,x,g):
    q = deque()
    q.append([y,x])
    visited[y][x] = True
    while q:
        y,x = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and g[ny][nx] == 1 and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append([ny,nx])


for i in range(101):        # 높이가 1부터 100이하라고 했으므로 101번 반복
    temp = find_safety(i)   # 높이에 따라 변경된 안전지역 그래프를 temp에 저장
    visited = [[False]*N for _ in range(N)] # 방문 여부를 확인하기 위한 visited 이중 배열
    count = 0               # 안전지역 개수 세는 변수
    for j in range(N):
        for k in range(N):
            if temp[j][k] == 1 and not visited[j][k]:
                bfs(j,k,temp)
                count += 1
    answer.append(count)
print(max(answer))