dfs

문제https://www.acmicpc.net/problem/11725풀이해당 문제는 루트 없는 트리에서 각 노드의 부모를 찾아야 한다. 트리의 루트를 1로 정했을 때, 각 노드의 부모를 구하여 출력해야 한다. 우선 노드의 개수인 N을 입력받고, 이후 N-1개의 줄에서 두 노드의 연결 정보를 인접 리스트 구조로 입력는다.그리고 DFS를 시작하여 루트 노드(1)를 방문 처리하고, 연결된 모든 노드를 탐색하면서 각 노드의 부모 노드를 찾는다. DFS는 재귀적으로 호출되며, 현재 노드를 방문 처리하고, 연결된 노드 중 방문하지 않은 노드를 탐색하면서 부모 노드를 설정한다. 모든 노드의 부모를 찾은 후, 2번 노드부터 순서대로 부모 노드를 출력한다. Codeimport java.io.*;import java.u..

문제https://www.acmicpc.net/problem/2668풀이문제를 보면 표는 두 줄로 구성되어 있으며, 첫째 줄에는 1부터 N까지의 숫자가 순서대로, 둘째 줄에는 임의의 1이상 N 이하의 숫자가 들어 있다. 첫째 줄에서 숫자를 선택해서, 선택한 숫자들과 그 아래 둘째 줄의 숫자들이 이루는 집합이 일치해야 한다. 그리고 선택된 숫자들의 개수가 최대가 되어야 한다. 각 숫자에서 시작하여 둘째 줄의 숫자를 따라가다가 출발 숫자를 다시 만나면 사이클이 형성된다. 사이클을 찾기 위해 DFS를 사용했다. 각 숫자의 출발점으로 DFS를 수행하여 사이클을 찾아내고, 그 사이클에 속하는 숫자들을 결과 리스트에 추가한다.DFS 탐색 중에 각 숫자가 여러 번 방문되지 않도록 방문 처리를 하고, 각 탐색이 끝난 ..

문제https://www.acmicpc.net/problem/24480풀이이 문제는 그래프의 정점을 입력받아서 해당 정점들만 탐색하면 되므로 인접 리스트를 사용하는게 적절하다고 판단했다. 이번에는 이중 ArrayList를 사용하여 풀어봤다. 그래프의 내용을 저장할 ArrayList> graph를 만들어서 간선 정보를 입력받는다. 그리고 DFS를 이용하여 시작 정점에서 탐색을 시작한다. 각 정점을 방문할 때, 방문한 순번을 배열에 저장하고, DFS 탐색이 끝나면 저장했던 순번을 출력한다. 매우 사소한 실수로 메모리 초과가 발생했다...Codeimport java.io.*;import java.util.*;/*- 정점과 간선의 정보를 이용해서 출발 정점에서 각 정점을 방문하는 순번을 결과로 출력한다.- 시작..

문제https://www.acmicpc.net/problem/1012풀이graph를 생성하여 값들을 모두 입력 받고, for문으로 graph를 탐색하면서 graph의 현재 위치가 1(배추)이며, visited(방문하지 않은 곳)의 값이 false이면, dfs 또는 bfs를 실행하여 해당 지점을 기준으로 연결된 부분들을 방문처리하고 애벌래 개수를 증가시킨다. Dfs와 Bfs 모두 풀이가 가능하여 두 가지 방법으로 풀어보았다.CodeDfs 적용 (주석 변경으로 Bfs로도 적용 가능)import java.io.*;import java.util.ArrayDeque;import java.util.StringTokenizer;public class Main { static int T, M, N, K; s..