백준_python 2468번 안전 영역 (BFS, DFS, 부르트포스 그래프)

<문제 링크>

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

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

 

 

 

<정답 코드>

🔷 sol 1) DFS_재귀(Recursion)

import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
 
# 상하좌우 좌표
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def dfs(x, y, h, visited):
    visited[x][y] = True
 
    for m in range(4):
        nx = x + dx[m]
        ny = y + dy[m]
 
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and ground[nx][ny] > h:
            dfs(nx, ny, h, visited)
 
# 입력
n = int(input())
ground = [list(map(int, input().split())) for _ in range(n)]
 
max_height = max(max(row) for row in ground)    # 땅의 최대 높이 계산
answer = 1              # 최소 한 개의 안전 구역이 항상 존재
 
for k in range(1, max_height + 1):
    visited = [[False] * n for _ in range(n)]
    safe = 0
    for i in range(n):
        for j in range(n):
            if ground[i][j] > k and not visited[i][j]:
                safe += 1
                dfs(i, j, k, visited)
    answer = max(answer, safe)
 
print(answer)

 

 

🔷  sol 2) DFS_스택

# dfs_stack
def dfs(x, y, h, visited):
    visited[x][y] = True
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        for m in range(4):
            nx = cx + dx[m]
            ny = cy + dy[m]
 
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and ground[nx][ny] > h:
                visited[nx][ny] = True
                stack.append((nx, ny))

 

 

 

🔷  sol 3) BFS

import sys
from collections import deque
input = sys.stdin.readline
 
# 상하좌우 방향벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
# bfs
def bfs(x, y, h, visited):
    visited[x][y] = True
    q = deque([(x,y)])
    while q:
        cx, cy = q.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and ground[nx][ny] > h:
                visited[nx][ny] = True
                q.append((nx, ny))
 
n = int(input())
ground = [list(map(int, input().split())) for _ in range(n)]
max_height = max(max(row) for row in ground)    # 땅의 최대 높이 계산
answer = 1              # 최소 한 개의 안전 구역이 항상 존재
 
for k in range(1, max_height + 1):
    visited = [[False] * n for _ in range(n)]
    safe = 0
    for i in range(n):
        for j in range(n):
            if ground[i][j] > k and not visited[i][j]:
                safe += 1
                bfs(i, j, k, visited)
    answer = max(answer, safe)
 
print(answer)

 

 

 

<채점 결과 및 정리>

 

처음에는 DFS 문제라고 생각하고 재귀로 풀었는데 가장 비효율적인 방법이었다. 

메모리 사용에는 큰 차이가 없지만, 스택을 이용한 DFS나 BFS가 효율적인 문제였다.

그래프 문제에서 DFS의 두 가지 방법과 BFS를 자유롭게 구현할 수 있도록 연습해야겠다. 

 

모든 경우는 아니지만 재귀를 통한 DFS가 비효율적인 상황이 있다.

이유와 상황을 정리하면 아래와 같다. 

 

 

🔷 재귀를 통한 DFS가 비효율적인 이유

• 함수 호출 오버헤드
  • 함수 호출할때마다 호출 stack에 새로운 프레임 추가
  • 이 과정에서 추가 메모리 할당과 실행 메모리 주소 저장하는 오버헤드 발생
• 스택 오버플로우
  • 깊은 재귀가 발생할 경우 스택 오버플로우 발생 가능
  • 깊이가 매우 깊은 트리/그래프 탐색 식 사용 유의
• 메모리 사용 효율성
  • 각 호출마다 로컬변수, 매개변수 등을 스택에 저장해야 하므로 메모리 사용 많을 수 O