깊이 우선 탐색4

• [백준/BOJ] 11725번: 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 DFS를 이용하여 해결할 수 있는 문제이다. 트리 상에 연결되는 두 정점이 부모-노드 구분이 없기 때문에 양방향으로 넣어줘야한다. 또한 문제에서 트리의 루트를 1이라고 정했기 때문에, 1은 먼저 방문처리 해준 후, DFS를 실행시킨다. 소스 코드 private lateinit var arr: Array private lateinit var parent: IntArray private lateinit var visited: BooleanArray fu.. PS(Problem Solving)/BOJ 2022. 7. 23.

• [백준/BOJ] 4963번: 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테.. PS(Problem Solving)/BOJ 2022. 6. 20.

• [백준/BOJ] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 1.. PS(Problem Solving)/BOJ 2022. 6. 14.

• 

  [알고리즘] 그래프 탐색(Graph Search) /BFS, DFS 그래프 그래프란 공집합이 아닌 노드(vertex, node)들의 유한 집합 V와 이 노드들을 연결하는 간선(edge)들의 집합 E로 구성된다. -> G = (V, E), |V| = n, |E| = m 트리는 그래프의 한 종류이다. 그래프에서 사이클이 존재하지 않으면 곧 트리이다. 노드의 차수: 노드에 연결된 간선의 수를 말하며, 방향 그래프에서는 진입 차수(indegree)와 진출 차수(outdegree)로 나누어 고려한다. 경로(path): 두 개의 노드를 연결하는 일련의 노드들 - 노드 a에서 b까지의 경로 a, v1, v2, . . . , vk, b가 존재하기 위해서는 간선 (a, v1), (v1, v2), . . ., (vn-1, vk), (vk, b)가 존재해야 한다. - 단순 경로: 한 노드를.. Algorithm 2022. 6. 2.