DFS

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 (0,0)에서 (N-1,N-1)까지의 인덱스에서 상하좌우 방향으로 dfs를 수행한다. dfs 탐색은 상하좌우 방향의 인덱스를 대상으로 방문하지 않았으면서 해당 위치의 값이 기존의 인덱스에서의 값과 일치할 때 탐색을 수행한다. 이 문제에서는 적록색약인 경우와 아닌 경우 두 가지 경우에서 나뉜 구역의 수를 구해야 하므로dfs를 구현한 함수의 매개변수에 ..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 1. 이중 ArrayList를 사용하여 각 노드가 가지고 있는 자식 노드의 번호를 저장한다. 2. 각 노드들의 부모 노드 번호를 저장하는 배열을 만든다. 3. 제거한 노드의 부모노드에 대응되는 ArrayList에서 제거한 노드의 번호를 삭제한다. 4. DFS를 통해 트리를 탐색하고, 방문한 노드 중 자식 노드가 없는 경우 count를 1씩 더한다. 제..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 싸이클이 발생하는 노드들을 모아 오름차순으로 출력해주면 되는 문제다. 1. DFS를 통해 각 노드마다 싸이클이 발생하는지 판단한다. - DFS 탐색 중, 탐색의 첫 번째 노드와 동일한 노드로 탐색을 하게 되면 싸이클이다. 2. 싸이클이 발생하면 탐색과정의 모든 노드 번호들을 TreeSet에 삽입한다. 3. 첫번째 노드부터 마지막 노드까지 2번 ..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net import sys sys.setrecursionlimit(10**5) n,m,r=map(int,sys.stdin.readline().split()) visited=[0 for _ in range(n+1)] graph=[[] for _ in range(n+1)] cnt=1 def dfs(start): global cnt vi..