https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 설명 케빈 베이컨의 수가 가장 작은 사람을 구하면 된다. 케빈 베이컨은 다른 사람을 알기 위해 걸치는 다리 수를 말한다. 예를 들면 다음과 같다. A, B, C, D, E가 있고 A와 C, A와 D, B와 C, C와 D, D와 E가 친구인 경우를 생각해보자. 발그림 죄송합니다 A의 케빈 베이컨을 구하면 다음과 같다. B를 알기 위해 C를 거쳐야..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 설명 BFS를 활용한 구현 문제이다. 조건이 많아 문제를 잘 이해해야 한다. 문제에서 주어진 물고기를 먹는 조건은 다음과 같다. 아기 상어는 자신보다 큰 물고기는 먹을 수 없으며 공간 또한 지나갈 수 없다. 자신과 같은 크기의 물고기는 먹을 순 없지만 지나갈 수 있다. 자신보다 작은 물고기는 먹을 수 있다. 아기 상어의 이동 조건은 다음과 같다. 더 이상 먹을 수 있는 물고기가 없다면..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 설명 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하면 된다. DFS와 BFS를 조합해야 할 거 같다는 생각은 들었는데 구현이 되지 않아 다른 풀이글을 참고했다. 핵심은 방문 기록을 매 반복마다 새로 사용하는 것이었다. 지금까지 풀어온 문제들은 한 번의 순회로 모두 해결되었었는데 이번 문제는 방문 기록을 매번 새로 사용..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 벽 3개를 모두 사용하여 안전 구역을 최대한 많이 만드는 문제이다. 풀이 방법 DFS와 BFS를 혼합하여 사용한다. 먼저 DFS로 벽을 세우고, BFS로는 바이러스를 전파한다. 그렇게 만들어진 안전 구역을 구해가면서 최댓값을 구한다. 먼저 DFS 코드부터 확인하자. private static void buildWall(int count) { if (count == 3) { processMainLog..

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) 풀이..