문제 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 입력받은 배열의 모든 지점에서 출발하는 DFS(깊이 우선 탐색)를 수행하고 각 DFS에서는 현재 위치에서 상하좌우도 이동하여 새로운 숫자를 만들어 나간다. DFS의 깊이가 6이 되면 탐색을 종료하고, 탐색으로 찾은 6자리 숫자를 HashSet에 저장한다. HashSet은 중복을 제외하기 기 때문에 HashSet의 크기는 탐색으로 발견 가능한 모든 수의 개수가 된다. 코드 fun main() { val br =..

문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 BFS나 DFS를 활용해 풀이하면 된다. 탐색에는 방문을 확인하는 visited 배열과 얼마나 녹을지를 저장하는 melted 배열을 이용한다. 탐색은 빙산을 기준으로 하며 방문 지점이 0보다 클 때 visited 배열에 방문 표시를 하고 이어서 탐색해준다. 0 이하인 경우에는 현재 위치의 melted 배열에 1을 증가해준다. 탐색하는 횟수를 세어 2 이상인 경우에는 빙산이 분리된 것이므로 반복문을 종료하고 시간을 출력해준다. 0인 경우에는 빙산이..

문제 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 DFS를 활용해 순열 사이클을 구할 수 있다. 입력받은 배열에는 다음으로 이동할 위치를 가르키고 있기 때문에 현재 위치는 방문 표시를 해주고 가르키는 위치로 DFS 탐색을 해주면 된다. 만약 현재 위치에서 가르키는 위치가 이미 방문했던 위치인 경우, 순열 사이클이 만들어진 것이다. 반복문을 통해 각 위치에서 시작하는 사이클을 구하면 되는데, 이미 방문했던 위치는 사이클에 포함되어 ..

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 이 문제는 5명의 친구관계가 연결되어 있는 것을 찾는 문제로, DFS와 백트래킹을 이용하여 depth가 5인 관계를 찾으면 된다. 먼저, 친구관계를 입력받아 양방향으로 연결된 그래프를 생성한다. 그리고 모든 노드에 대한 DFS 탐색을 수행한다. DFS 탐색은 백트래킹을 이용하여 방문했던 노드에서 연결된 노드가 있을 경우 방문 체크를 해준 뒤 DFS를 수행한다. DFS 수행 이후 방문한 노드의 상태를 방문하지 않은 것으로 다시 바꿔준다. 탐색 중 DFS의 depth가 5가 되는 경우, 5명의 친구가 연결되었다고 판단하고 check 변수를 true로 만들어 준다..

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 이 문제의 풀이 과정과 사용한 알고리즘은 다음과 같다. 1. 섬에 고유 번호 부여 (DFS): 입력받은 지도를 DFS나 BFS를 이용하여 각 섬에 번호를 부여해준다. 입력에서 1이 섬이기 때문에 첫번째 섬부터 2번으로 부여해주었다. 2. 각 섬을 연결할 수 있는 방법 구하기 (BFS): 각 섬을 연결하는 가능한 모든 다리를 찾아준다. 길이가 1보다 큰 다리들을 거리에 따라 오름차순으로 정렬될 수 있게 우선 순위 큐에 저장한다. 3...