백준2468 - 안전 영역 (DFS) Python

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

해당 문제는 주어진 2차원 배열에서, 수심에 따른 안전 지역의 갯수를 구한 뒤 최댓값을 출력하는 문제다.

구역을 나누는 방식에는 DFS 알고리즘이 익숙하기 때문에 해당 알고리즘으로 접근했다.

 

풀이 방식은 다음과 같다.

먼저 수심에 따른 안전지대의 갯수를 구하는 것이므로, 수심의 범위를 제한하는 과정이 필요하다.

그리고 수심의 범위는 2차원 배열이 가진 최솟값과 최댓값 사이이기 떄문에,

 

해당 이차원 배열에서 나올 수 있는 수심 즉 깊이는 2차원 배열이 가진 최솟값 이상 최댓값 이하이기 때문에,

아래와 같이 미리 변수를 선언해두었다.

 n = int(data.pop(0))
 matrix = [list(map(int, v.split())) for v in data]
 _max, _min = max(map(max,matrix)), min(map(min,matrix))

 

이후 안전 지대를 찾는 로직인데, 이는 수심의 최솟값에서부터 최댓값까지 DFS 알고리즘을 활용하여 진행한다.

  result = 0
  # 최솟값 ~ 최댓값 사이인 수심 k
  for k in range(_min - 1, _max) :
    _safe = 0 # 안전 지대 갯수
    visited = [[0] * n for _ in range(n)] # 방문 기록
    for i in range(n) :
      for j in range(n) :
        # 해당 수심을 초과하고 방문하지 않은 경우에 DFS 로직 실행 및 안전지대 + 1
        if matrix[i][j] > k and not visited[i][j] :
          _safe += 1
          DFS(matrix,j,i,_safe,k,visited)
    result = max(result, _safe)
  print(result)  
  
def DFS (matrix,x,y,_safe,k,visited) :
  X,Y = len(matrix[0]), len(matrix)
  stack = [[x,y]]
  while stack :
    x,y = stack.pop()
    visited[y][x] = _safe
    
    direction = [[-1,0], [1,0], [0,-1], [0,1]]
    for dx, dy in direction :
      nx,ny = dx+x, dy+y
      # 유효 영역인지 | 다음 이동할 영역이 정한 수심을 초과하는지 | 방문하지 않았는지 검증
      if verify(nx,ny,X,Y) and matrix[ny][nx] > k and not visited[ny][nx] :
        stack.append([nx,ny])
  
def verify (x,y,X,Y) :
  return 0 <= x < X and 0 <= y < Y

 

개인적인 취향이지만 DFS 알고리즘은 재귀 함수보다 while문으로 구현하는 것을 선호한다.

재귀 함수 그 자체가 그만큼 스택 영역에 많은 메모리를 할당하는 것이기 때문에, 좋은 방법은 아닐 것이라고 생각한 까닭.

추가적으로 BFS 알고리즘도 while문을 사용하여 대부분 구현하다보니 일관성 측면에서도 좋기도 하다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  n = int(data.pop(0))
  matrix = [list(map(int, v.split())) for v in data]
  _max, _min = max(map(max,matrix)), min(map(min,matrix))
  
  result = 0
  for k in range(_min - 1, _max + 1) :
    _safe = 0
    visited = [[0] * n for _ in range(n)]
    for i in range(n) :
      for j in range(n) :
        if matrix[i][j] > k and not visited[i][j] :
          _safe += 1
          DFS(matrix,j,i,_safe,k,visited)
    result = max(result, _safe)
  print(result)  
  
def DFS (matrix,x,y,_safe,k,visited) :
  X,Y = len(matrix[0]), len(matrix)
  stack = [[x,y]]
  while stack :
    x,y = stack.pop()
    visited[y][x] = _safe
    
    direction = [[-1,0], [1,0], [0,-1], [0,1]]
    for dx, dy in direction :
      nx,ny = dx+x, dy+y
      if verify(nx,ny,X,Y) and matrix[ny][nx] > k and not visited[ny][nx] :
        stack.append([nx,ny])
  
def verify (x,y,X,Y) :
  return 0 <= x < X and 0 <= y < Y

solution(input_data)