[Baekjoon] 2468번 : 안전 영역 (Python, 그래프, DFS, BFS)

[Baekjoon] 2468번 : 안전 영역 (Python, 그래프, DFS, BFS)

 

목차

 

 

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

2468번: 안전 영역

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 40748KB / 시간 1472ms / 코드 길이 688B

 

0~최대 높이에 해당하는 침수에 대하여 진행하고 각 진행은 매번 지정 침수 높이보다 큰지 방문은 했는지를 통해서 확인하는 작업을 진행한다.

이때 DFS, BFS를 통해 방문 처리를 용이하게 한다.

 

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

def dfs(x,y, val):
    visit[x][y] = 1
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if l[nx][ny] > val and visit[nx][ny] == 0:
                dfs(nx, ny, val)
    return 1

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
max_n = max(map(max, l))
res = 0
for h in range(max_n):
    cnt = 0
    visit = [[0]*n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if l[i][j] > h and visit[i][j] == 0:
                cnt += dfs(i, j, h)
    res = max(res, cnt)
print(res)

 

방법 2 - 메모리 40748KB / 시간 1316ms / 코드 길이 703B

 

방법 1 이전 초기 버전

 

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

def dfs(x,y):
    visit[x][y] = 0
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny]:
            dfs(nx, ny)
    return 1

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
res = 0
for h in range(101):
    cnt = 0
    visit = [[0]*n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if l[i][j] > h:
                visit[i][j] = l[i][j]

    for i in range(n):
        for j in range(n):
            if visit[i][j]:
                cnt += dfs(i,j)

    res = max(res, cnt)
print(res)