https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 설명 기본적인 DFS 문제이다. 1번 노드에서 2번 노드까지 얼마나 간선을 거치는지를 구하면 된다. 조심할 점은 가족이 아닌 경우 -1을 출력해야 한다는 점이다. 풀이 방법 1. DFS public static void main(String[] args) throws IOException { // ... dfs(targets[0], 0); // ... } private s..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 제목이 트리의 부모 찾기라서 트리를 구현해야 하나 싶지만 인접 리스트 그래프로 복잡하지 않게 해결할 수 있다. 트리도 그래프의 부분집합이다. 사이트 예제 1을 활용하여 그려보면 다음과 같다. 각 노드의 부모를 구하는 게 문제이기 때문에 DFS나 BFS로 루트(1)부터 연결된 노드들을 탐색해 나가면 된다. 위 그림을 토대로 코드의 흐름을 그려보면 다음과 같다. DFS(1) DFS(6) DFS(3) DFS(5) DFS(4) DFS(2) DFS(7) 풀이..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 설명 DFS 문제를 살짝 응용한 문제이다. 풀이 방법 핵심이 되는 DFS 함수는 다음과 같다. private static void dfs(int r, int c, int count) { if (isDuplicated[board[r][c]]) { MAX = Math.max(MAX, count); return; } else { isDuplicated[board[r][c]] = true; ..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 설명 기본적인 DFS 문제이다. 크게 설명할 것은 없으며 주의할 점은 대각선까지 하나의 섬으로 따지는 것이다. 풀이 방법 기본적인 DFS 방식으로 해결할 수 있다. package baekjoon.dfs_bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 설명 기본적인 DFS 문제이다. RGB 픽셀로 이루어진 입력이 주어지고 일반 사람과 적록색약이 볼 수 있는 구역의 수를 구하면 된다. 풀이 방법 일반인과 적록색약이 보는 그림을 구분하기 위해 먼저 두 개의 배열을 준비하고 입력받았다. 적록색약의 그림은 G를 R로 대신 입력하면 된다(또는 그 반대). for (int x = 0; x < N; x++) { char[] pixels = br..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 설명 수열과 연산자들이 주어지고 그 모든 조합을 찾아 최댓값과 최솟값을 구하는 문제이다. 모든 경우를 탐색해야 하므로 완전탐색 문제이다. 풀이 방법 이 문제는 재귀를 활용하여 해결할 수 있다. 해결 방법이 DFS와 같은 방식이다. 종료 조건은 인덱스와 N의 값이 같을 때인데 N과 같다면 더 이상 할 연산이 없기 때문이다. 그리고 반복이 ..