[백준/DFS-BFS] 2468: 안전 영역 - 파이썬

문제

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

2468번: 안전 영역

 

풀이

1. 지역의 높이를 리스트로 입력받으면서 가장 큰 값을 찾음
2. 1부터 가장 큰 값까지 물에 잠기지 않는 범위를 DFS/BFS 알고리즘을 통해 찾아서 결과 리스트에 저장
3. 결과 리스트 중에서 가장 큰 값이 문제에서 찾고자 하는 답.

# DFS 사용
import sys
sys.setrecursionlimit(100000)

n = int(input())
graph = []
max_num = 0
result = 1

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

for i in range(n):
    low = list(map(int, input().split()))
    graph.append(low)

    for j in low:
        if j > max_num:
            max_num = j

def dfs(x,y,num):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<n and 0<=ny<n and visited[nx][ny] == 0:
            if graph[nx][ny] > num:
                visited[nx][ny] = 1
                dfs(nx,ny,num)

for i in range(max_num):
    visited = [[0]*n for _ in range(n)]
    cnt = 0

    for j in range(n):
        for k in range(n):
            if graph[j][k] > i and visited[j][k] == 0:
                cnt += 1
                visited[j][k] = 1
                dfs(j,k,i)
    result = max(result, cnt)

print(result)

DFS 방법을 이용할 때 재귀 방식으로 풀었는데 재귀를 100000으로 제한 해제하여 풀어야 함.

 

다음은 BFS 방법을 통하여 구하였음.

from collections import deque

n = int(input())
max_num = 0
graph = []

for _ in range(n):
    low = list(map(int, input().split()))
    graph.append(low)

    for i in low:
        if i > max_num:
            max_num = i

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

def bfs(x, y, num):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > num and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))

result = []

for i in range(max_num):
    cnt = 0
    visited = [[0]*n for _ in range(n)]
    for j in range(n):
        for k in range(n):
            if graph[j][k] > i and visited[j][k] == 0:
                bfs(j, k, i)
                cnt += 1
    result.append(cnt)

print(max(result))