https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 문제 설명 바닥 장식을 위한 타일 개수를 카운팅하는 문제이다. 단, -- 과 같이 이어져 있다면 하나의 타일로 간주한다. 풀이 방법 DFS를 활용하여 문제를 해결했다. 이어져 있는 타일의 끝까지 간 후에 카운팅하면 되기 때문이다. 고려해야 할 점은 바닥면의 끝부분에 닿은 상황이다. 이 경우에는 타일을 더 놓을 수 없으므로 해당 칸에서 DFS를 종료시킨다. private static void dfs(int..

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/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 설명 첫 칸에서 마지막 칸까지 갈 수 있는 모든 경로의 수를 구하면 된다. 단, 항상 높이가 더 낮은 지점으로만 이동한다. 풀이 방법 1. DFS -> 시간 초과 보자마자 DFS로 풀면 되겠다고 생각했고 바로 코딩에 들어갔다. 코딩하면서 이게 왜 정답률이 27%밖에 안 되지? 생각했었는데 왜 그런지 코드를 제출해보고 알게 되었다. private static void dfs(int x, int y)..

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