백준 2468 안전 영역 Python 3

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

2468번: 안전 영역

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2468.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline

def dfs(x, y, h):
    global visit
    for ddx, ddy in zip(dx, dy):
        nx = x + ddx
        ny = y + ddy
        if 0 <= nx < N and 0 <= ny < N and area[ny][nx] > h and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny, h)

N = int(input())
area = []
max_area = 0
max_height = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for _ in range(N):
    row = list(map(int, input().split()))
    area.append(row)
    highest = max(row)
    if max_height < highest: max_height = highest

for h in range(max_height+1):
    visit = [[0]*N for _ in range(N)]
    now_area = 0
    for y in range(N):
        for x in range(N):
            if area[y][x] > h and not visit[y][x]:
                visit[y][x] = 1
                dfs(x, y, h)
                now_area += 1
    if now_area > max_area: max_area = now_area
print(max_area)

---

풀이 과정

풀이 시간 14분

import sys
#최대 100x100 그래프 탐색해야 하므로 재귀 제한 늘린다
sys.setrecursionlimit(20000)
input = sys.stdin.readline

def dfs(x, y, h):
    global visit
    for ddx, ddy in zip(dx, dy):
        nx = x + ddx
        ny = y + ddy
        
        #범위 안에 있으면서, h보다 높은 지역이고 이전에 방문하지 않았다면 탐색을 이어간다
        if 0 <= nx < N and 0 <= ny < N and area[ny][nx] > h and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny, h)

N = int(input())
area = []

#안전한 영역의 최대 개수
max_area = 0
#지역의 최대 높이
max_height = 0

#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for _ in range(N):
    row = list(map(int, input().split()))
    area.append(row)
    highest = max(row)
    #가장 높은 지역의 높이를 구한다
    if max_height < highest: max_height = highest

#가능한 비의 높이 h를 설정하고 잠기는 영역을 탐색한다
for h in range(max_height+1):
    visit = [[0]*N for _ in range(N)]
    
    #비의 높이가 h일 때 잠기지 않은 영역 개수
    now_area = 0
    for y in range(N):
        for x in range(N):
        	#h보다 높은 지역이면서 이전에 탐색하지 않았다면, 새 영역을 탐색한다
            if area[y][x] > h and not visit[y][x]:
                visit[y][x] = 1
                dfs(x, y, h)
                #영역 개수 카운팅
                now_area += 1
                
    #최대 영역 개수 갱신       
    if now_area > max_area: max_area = now_area
    
print(max_area)

#시간복잡도 = O(V+E), 공간복잡도 = O(n)