기록방

👉 문제링크🔸 문제 분석 🔸바닷물과 맞닿은 빙하는 1년마다 상하좌우의 바닷물 수 만큼 줄어든다.빙하가 두 덩어리 이상으로 나뉘어지는 최소 시간을 출력한다.끝까지 두 덩어리가 되지 않으면 0을 출력한다.🔸 문제 풀이 🔸빙하가 녹는건 4방탐색을 하면 되고, 덩어리 확인은 그래프 탐색과 4방 탐색을 함꼐 하면 된다.여기서는 그래프 탐색 알고리즘으로 너비 우선 탐색 (BFS) 를 사용했다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;public class Main { private static int N, M; private static int..

👉 문제링크 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🔸 문제 분석 🔸 무방향 그래프가 주어지면, 이분 그래프인지 아닌지 판별한다. 🔸 문제 풀이 🔸 그래프 탐색을 통해 각 노드가 서로 다른 집합에 속하는지 구분한다. DFS로 처음 방문한 노드에 한번은 A집합, 한번은 B집합으로 번갈아 가며 포함시킨다. 이미 방문한 노드인데, 같은 집합이면 이분 그래프가 아니다. 여러 개의 부분 그래프로 이루어 져있을 수 있으므로, 모든 노드에서 DFS를 시작해본다. 모든 탐색 이후 이분 그래프 판정 결과를 출력한다...

👉 문제링크 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🔸 문제 분석 🔸 N x M 모눈종이에 공기와 치즈가 0, 1 로 주어진다. 외부 공기와 2개 이상 맞닿은 치즈는 녹는다. 치즈가 모두 녹는데 걸리는 시간을 구한다. 🔸 문제 풀이 🔸 치즈 내부의 공기와 외부 공기를 분리해서 생각한다. 가장자리 면은 치즈를 두지 않는다고 문제에서 제한했으므로, (0,0)부터 그래프 탐색으로 인접한 0을 2로 바꾼다. 풀이에선 DFS를 사용했다. 공기와 맞닿은 치즈를 녹여 없앤다. 치즈가 녹은 자리는 공기..

👉 문제링크 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 🔸 문제 분석 🔸 노드 사이 거리(가중치)가 있는 트리에서 가장 먼 거리를 구한다. 어느 부분 가중치가 큰 값이든 트리의 지름 양 끝은 리프 노드일 것이다. (큰 가중치 부분을 반드시 지남) 트리이기 때문에 두 노드 사이의 경로는 하나로 유일하다. 한 노드에서 가장 먼 노드를 구하면, 그 노드가 트리의 지름 양 끝 리프 노드 중 하나이다. DFS 두 번으로 풀이할 수 있다. DFS 1 : 아무 노드에서 가장 먼 노드를 구한다. DFS..

👉 문제링크 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 🔸 문제 분석 🔸 트리의 루트 노드와 각 인덱스 별 노드의 부모 노드 정보가 입력된다. 한 노드를 지우면 아래 자손 노드들이 모두 지워진다. 남은 리프노드의 수를 출력한다. 인접 리스트를 만들어 연결 정보를 저장한다. 만약 아직 부모노드가 등장하지 않았다면, 큐에 넣고 순서를 기다린다. 삭제할 때 DFS를 사용해 자식 노드를 모두 삭제한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOExc..