코딩테스트 알고리즘 - DFS(백준 2667, 단지번호 붙이기)

DFS? 그래프 탐색의 방법

그래프 탐색은 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법

--> 즉 Vertex와 Edge. 정점과 간선들이 있을 때 모두 확인하는 문제를 그래프 탐색이라고 한다.

 

그래프 탐색에는 크게 두 가지

BFS : Breadth - first search(너비 우선 탐색)

DFS : Depth - first search(깊이 우선 탐색)

 

BFS는 자기 형제들을 먼저 확인한다. 무슨 말이냐? 

화질뭐노

 

위와 같이 자기 형제들을 다 거친후 그 자식들을 가는게 BFS,

한 자식의 끝까지 갔다가 다음으로 계속 넘어가는게 DFS.

그래서 아래 그림을 보면

 

BFS 같은 경우는 A B C D E F 순으로 탐색하고,

DFS는 A D F C E B 순으로 탐색한다

 

연결된 노드를 탐색하는건 BFS로도 충분하다 근데 왜 DFS?

재귀함수를 위해 --> BackTracking에서 중요. DFS로 재귀함수 익힌다고 생각하자.

 

DFS는... 

재귀함수로 푸는 방식, Stack으로 푸는 방식 두 가지가 있다

 

재귀함수 : 자기 자신을 다시 호출하는 함수

주의할 점 ?

 - 재귀함수가 종료되는 시점을 반드시 명시해야 한다

 - 재귀함수의 깊이가 너무 깊어지면 Stack Overflow

 --> DFS, BackTracking에서 주로 사용

 

Stack을 쓰는 이유는?

최근 Stack에 넣은 것 먼저(가장 깊은 것 먼저) 빼낸 후 들르기 때문에 Stack 자료구조가 필요한 것

 

DFS 아이디어?

 - 시작점에 연결된 Vertex 찾기

 - 연결된 Vertex를 계속해서 찾음(끝날때 까지)

 - 더 이상 연결된 Vertex 없을 경우 다음

 

시간복잡도

DFS : O(V+E)의 시간복잡도

즉 최대의 Vertex 개수 + Edge 개수가 DFS의 시간복잡도이다

 

자료구조?

검색할 그래프, 방문여부 확인

 

DFS 기본문제인 2667번 문제로 DFS를 설명해보자.

 

 

'''

1. 아이디어

- 2중 for문 돌면서, 값이 1인 것 && 방문X => DFS

- DFS를 통해 값 찾은 것 cnt 후 정렬 해 리턴

2. 시간복잡도

- DFS : O(V+E)

- V, E = N^2, 4N^2

- V+E = 5N^2 = N^2 --> 25 * 25 = 625 < 2억 보다 한참 아래

3. 자료구조

- 그림 ground 2차원 배열

- 방문여부 bool 2차원

- 결과값 저장 int list cnt []

'''

import sys

input = sys.stdin.readline

n = int(input())

graph = []

for i in range(n) :

     # 공백 없는 입력 분할해 저장하기 위해 list(input().rstrip())

     graph.append(list(map(int, list(input().rstrip()))))

visited = [[False] * n for _ in range(n)]

# 영역

sizes = []

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

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

def DFS(y, x) :

     global size

     size += 1

     for a in range(4) :

          ny = y + dy[a]

          nx = x + dx[a]

          if 0 <= nx < n and 0 <= ny < n :

               if graph[ny][nx] == 1 and visited[ny][nx] == False :

                    visited[ny][nx] = True

                    DFS(ny, nx)

for i in range(n) :

     for j in range(n) :

          if graph[i][j] == 1 and visited[i][j] == False :

               visited[i][j] = True

               size = 0

               DFS(i, j)

               sizes.append(size)

print(len(sizes))

sizes.sort()

for i in sizes :

     print(i)

위 코드처럼 작성해서 DFS로 풀어보았다. 순서를 정하는게 중요한 것 같은데

1. 우선 아이디어 작성

2. 시간복잡도 작성

3. 필요한 자료구조 작성

을 한 후 본격적으로 코드 작성을 하면 된다.

코드 작성에서도 룰을 좀 정해보자면

1. 입력값을 받는 자료구조 선언 및 작성

2. DFS에 필요한 자료구조 선언 및 작성

3. 2중 For문으로 탐색 작성

4. DFS 함수 작성

5. 리턴

 

순으로 작성했다.

 

BFS 응용문제는 많으니 문제 풀 때마다 이 게시물에 추가해야겠다.