코테 DFS

그래프 탐색 종류

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

자신의 자식이 우선

 

DFS는 재귀함수를 사용하기 위해함

백트래킹에서 재귀함수 개념이 매우 중요

 

재귀함수

• 자기 자신을 다시 호출하는 함수
• 주의할점
  • 재귀함수가 종료되는 시점 반듯이 명시
  • 재귀함수의 깊이가 너무 깊어지면 Stack Overflow
• DFS, 백트래킹에서 주로 사용 (그중 백트리킹에 많이 사용됨)

아이디어

• 시작점에 연결된 Vertex 찾기
• 연결된 Vertex를 계속해서 찾음(끝날 때 까지)
• 더이상 연결된 Vertex 없을 경우 다음 노드 찾음

시간복잡도

• 알고리즘이 얼마나 오래 걸리는지
• DFS : O (V+E)
• 검색할 그래프 : 2차원 배열
• 방문여부 확인 : 2차원 배열(재방문 금지)
• Queue를 사용하지 않음

백준 2667 그림 문제

 

1. 2중 for, 값 1 && 방문 X -> 재귀(DFS)

2. 값을 리스트에 저장

3. 정렬 이후 출력

import sys input = sys.stdin.readline N = int(input()) map = [list(map(int, input().strip())) for _ in range(N)] chk = [[False] * for _ in range(N)] result = [] each = 0 dy = 0,1,0,-1] dx=[1.0.-1.0] def dfs(y,x):     global each     each += 1     for k in range(4):         ny = y + dy[k]         nx = x + dx[k]         if 0 <=ny<N and 0 <=nx<N:             if map[ny][nx] == 1 and chk[ny][nx] == False:                chk[ny][nx] = Treu                dfs(ny, nx) for j in range(N):     for i in ragnge(N):          if map[j][i] == 1 and chk[j][i] == False:          chk[j][i] = True          each = 0          dfs(j, i)          result.append(each)         # 방문 체크 표시         # DFS로 크기 구하기         # BFS : 함수 호출, 리턴값으로 크기         # 크기를 결과 리스트에 넣기 result.sort() print(len(result)) for i in result:     print(i)