일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 자바스크립트
- 토익시험준비
- TOEIC문법
- NCS수리자료해석
- 너비우선탐색
- 매일매일NCS
- TOEIC
- 파이썬
- BFS
- 영문법
- sqld
- 토익단어
- 브루트포스
- 다이나믹프로그래밍
- 토익문법노트
- 토익 영단어
- 토익문법정리
- 알고리즘
- 데이터베이스
- 자료해석
- 영단어암기
- 문제해결능력
- 영어문장
- BOJ
- TOEIC Vocabulary
- 공기업공부
- 영단어
- 수리능력
- 주어
- dfs
- Today
- Total
목록dfs (3)
하나씩 알아가기
연결 요소(Connected Component)의 개수를 구하는 문제입니다. 인접행렬을 이용해서 풀 수 있습니다. 인접 행렬의 요소를 모두 확인할 것인데(n * n) 시작 노드부터 dfs 함수에 넣고 확인하는데 한 회차를 다 돌면 return하고 연결 요소 카운트를 올립니다. 1부터 n까지를 반복하는데 방문하지 않은 곳만 dfs에 넣습니다. n, m = map(int, input().split()) adj = [[0 for _ in range(n+1)] for _ in range(n+1)] visited = [False] * (n+1) result = 0 for _ in range(m): x, y = map(int, input().split()) adj[x][y] = 1 adj[y][x] = 1 def ..
틀린 부분이 있을 경우, 지적해 주시면 감사하겠습니다. 노드, 간선, 시작점을 첫째 줄에 입력 받고 둘째 줄 부터는 간선의 개수만큼 두 정점의 번호를 입력 받습니다. 두 개의 리스트를 생성합니다. 연결 정보를 나타낸 2차원 리스트 방문 여부를 기록한 1차원 리스트 이 정점을 연결 정보를 인접 행렬(adjacent matrix)로 다음과 같이 나타낼 수 있습니다. 0 1 2 3 4 1 1 1 1 2 1 1 3 1 1 4 1 1 연결이 되어 있다면 1을 넣어주었습니다. 가장 핵심이 되는 부분은 방문하지 않은 노드면서 연결이 되어있는 노드를 방문해 나가는 것인데 dfs의 경우 재귀함수를 호출하고 bfs일 때는 큐에다가 넣어줍니다 from collections import deque n, m, v = map(i..
DFS(Depth-First-Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 동작 과정 ① 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. ② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 ③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ※ 동작 원리는 스택이지만 구현은 재귀 함수를 이용해서 하는 것이 더 간결합니다. def dfs(graph, v, visited): #현재 노드를 방문처리 visited[v] = True print(v, end=' ') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in grap..