https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 간단한 그래프 탐색 문제. 알고리즘 분류에는 플로이드-와샬 이 포함되어 있는데, 간선 사이 가중치가 없고 i에서 j로 가는 경로가 있는지만 체크하면 되는 문제라 일반적인 DFS로 해결하였다. 인접행렬 형태로 받은 간선 정보를 이용하여 간선이 존재하는 기본 좌표를 [start, now] 형태로 stack에 넣어놓고 stack에서 하나씩 pop해 가며 DFS를 수행한다. 문제를 풀어보면서 아직 BFS보다 DFS 구현이 조금 낯선 느낌이 들었다..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net DFS와 BFS를 둘 다 연습해볼 수 있는 문제이다. 간단한게 DFS와 BFS의 풀이방식을 살펴보면 - DFS(깊이 우선 탐색): 스택 or 재귀를 사용해서 구현 - BFS(너비 우선 탐색): 큐를 사용해서 구현 나는 보통 DFS에서 재귀를 사용해서 구현하는데 파이썬의 경우 최대 재귀 횟수가 1000번으로 고정되어 있기 때문에 대부분의..