-
1260. [Python]DFS와 BFSPython_알고리즘/Silver II 2023. 8. 8. 12:12
1. 문제
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- DFS(깊이 우선 탐색)
- BFS(너비 우선 탐색
3. 파이썬 코드
# DFS 구현 함수 def DFS(graph, N, V): # N의 길이만큼 방문 체크 visited = [False] * N # graph 값들을 내림차순 정렬 for i in graph: i.sort(reverse=True) # stack 변수에 graph[시작노드][전체를 얕은 복사] 해주지 않으면 graph 자체가 수정되버림 stack = graph[V-1][:] # 처음 시작노드 True 처리 visited[V-1] = True # 처음 노드 answer 리스트에 저장 answer = [V] while stack: # stack 을 계속해서 뽑아내며 next_node = stack.pop() # 방문하지 않으면 stack 에 추가 및 visited 방문처리 후 answer 에 저장 if not visited[next_node]: stack.extend(graph[next_node]) visited[next_node] = True answer.append(next_node+1) return answer # 너비 우선 탐색 함수 def BFS(graph, N, V): # N 만큼 방문 체크 리스트 visited = [False] * N # 그래프 값들을 오름차순 정렬 for i in graph: i.sort() # stack 에 그래프 시작노드를 얕은 복사 stack = graph[V-1][:] # visited 시작값을 True 처리 visited[V-1] = True # answer에 시작값 넣기 answer = [V] while stack: # 첫번째 값들을 계속해서 뽑아줌 next_node = stack.pop(0) # 방문하지 않았으면 if not visited[next_node]: # 다음 노드를 추가, 방문처리, answer 리스트 값 추가 stack.extend(graph[next_node]) visited[next_node] = True answer.append(next_node+1) return answer N, M, V = map(int,input().split()) node_list= [] graph = [[] for _ in range(N)] for _ in range(M): nodes = list(map(int,input().split())) graph[nodes[0]-1].append(nodes[1]-1) graph[nodes[1]-1].append(nodes[0]-1) BFS_ans = BFS(graph, N, V) DFS_ans = DFS(graph, N, V) print(*DFS_ans) print(*BFS_ans)
4. 문제를 풀고난 후 생각
- 기본적으로 DFS와 BFS를 구현할 줄 아는지를 확인하는 문제로 개념을 정리 후 풀어보기 좋은 문제였던 것 같다.
5. 문제를 푸는데 도움이 되는 지식
- DFS(깊이 우선 탐색)
- BFS(너비 우선 탐색)
'Python_알고리즘 > Silver II' 카테고리의 다른 글
1564. [Python]팩토리얼5 (0) 2023.08.13 5397. [Python]키로거 (0) 2023.08.11 1874. [Python]스택 수열 (0) 2023.08.07 1541. [Python]잃어버린 괄호 (0) 2023.08.06 1024. [Python]수열의 합 (0) 2023.08.04