꼭 알아야하는 코딩 테스트 유형 : 15) #DFS

• 이번에는 코딩 테스트에서 반드시 알아야 하는 주제 중 하나인 깊이 우선 탐색(DFS, Depth-First Search)에 대해 이야기하려고 합니다. DFS는 그래프 탐색 방법 중 하나로, 시작 노드에서부터 가능한 한 깊숙히 들어가며 그래프를 탐색하는 방식입니다.

 

DFS(Depth-First Search)란?

 

• DFS는 그래프 탐색 알고리즘 중 하나로, 깊이를 우선으로 탐색하는 방식입니다. 시작 노드에서부터 한 경로를 따라 더 이상 갈 수 없을 때까지 탐색하고, 다시 돌아와서 다른 경로를 탐색합니다. 이 과정은 스택(Stack) 또는 재귀 함수를 통해 구현할 수 있습니다.
• DFS에서 사용되는 주요 개념은 다음과 같습니다.

 

1. 스택(Stack): DFS는 스택 자료구조를 활용하여 현재 위치에서 갈 수 있는 경로들을 저장하고 백트래킹(backtracking)합니다.
2. 재귀 함수(Recursion): 재귀 함수 호출을 통해 DFS를 구현할 수 있습니다.
3. 방문 여부 체크: 그래프의 각 노드나 정점을 방문했는지 여부를 체크하여 중복 방문을 방지합니다.

 

코딩 테스트에서의 DFS 문제 접근 전략

 

• 코딩 테스트에서 DFS 문제는 그래프나 트리와 관련된 문제, 백트래킹이 필요한 문제 등 다양한 상황에서 활용됩니다.
• 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용합니다.

 

1. 주어진 문제가 DFS 관련 문제인지 확인합니다.
2. 그래프 혹은 트리의 구조와 관련된 정보(인접 리스트, 인접 행렬 등)가 주어졌다면 이를 적절한 자료구조에 저장합니다.
3. 시작 지점 혹은 루트 노드로부터 출발하여 DFS 알고리즘을 적용합니다.
4. 스택이나 재귀 함수 호출 등을 활용하여 가능한 모든 경로들을 탐색하며 원하는 결과값을 찾거나 조건에 맞게 처리합니다.
5. 필요에 따라 백트래킹(Backtracking) 기법도 함께 사용하여 시간 복잡도를 줄일 수 있습니다.

 

1926번: 그림

  문제  

 

• 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

  해결 방법  
 

• 이 문제는 주어진 도화지에서 가장 큰 그림의 넓이와 전체 그림의 개수를 찾는 것입니다. 각 칸은 검은색(1) 또는 흰색(0)으로 채워져 있으며, 상하좌우로 연결된 검은색 칸들이 모여 하나의 그림을 형성합니다.
• 모든 좌표에 대해 아직 방문하지 않았고 검은색인 경우에만 DFS를 수행합니다.
• DFS 과정에서 방문한 칸들의 개수를 세어서 해당 그림의 넓이를 계산합니다. 그리고 가장 큰 넓이와 전체 그림의 개수를 출력합니다.

import sys; sys.setrecursionlimit(10000000); input=sys.stdin.readline

def dfs(x, y):
    global area
    board[x][y] = 0
    area += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if -1 < nx < n and -1 < ny < m and board[nx][ny] == 1:
            dfs(nx, ny)

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
result = []

for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            area = 0
            dfs(i, j)
            result.append(area)

if len(result) == 0:
    print(len(result))
    print(0)
else:
    print(len(result))
    print(max(result))

 
 

1937번: 욕심쟁이 판다

  문제  

 

• n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
• 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

 

  해결 방법  
 

• 이 문제는 판다가 최대한 많은 일수동안 대나무를 먹을 수 있는 기간을 찾는 것입니다. 판다는 자신의 위치보다 대나무가 더 많이 있는 곳으로만 이동할 수 있습니다.
• 모든 좌표에 대해 DFS를 수행하여 각 좌표에서 시작했을 때 생존 가능한 최대 일수를 구합니다.
• 이미 방문한 좌표에 대해서는 저장된 값을 재사용함으로써 중복 계산을 줄입니다. 최종적으로는 가장 큰 값을 출력합니다.

import sys; sys.setrecursionlimit(40000); input=sys.stdin.readline

def dfs(x, y):
    if dp[x][y]: return dp[x][y]
    dp[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
        if forest[nx][ny] > forest[x][y]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny)+1)
    return dp[x][y]

n = int(input())
forest = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
result = -1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(n):
    for j in range(n):
        result = max(result, dfs(i, j)) 

print(result)

 
 

• DFS 알고리즘은 그 자체로도 강력하지만 다른 알고리즘과 결합될 경우 훨씬 더 복잡한 문제를 해결할 수 있습니다. 앞으로도 다양한 코딩 테스트 문제를 해결하는 데 이러한 접근 방식을 활용하면 좋겠습니다.