기록방

👉 문제링크 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..

👉 문제링크 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 🔸 문제 분석 🔸 n * m 도화지에서 연결된 1의 개수의 최대값을 출력한다. BFS혹은 DFS로 연결된 1을 탐색한다. 연결된 1 무리의 개수와 그 중 최대값을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import..

👉 문제링크 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 🔸 문제 분석 🔸 R x C 크기의 2차원 배열의 0번 열부터 C-1번 열까지 파이프를 연결하고자 한다. '.' 에는 파이프를 놓을 수 있고, 'x'에는 놓을 수 없다. 첫 열과 끝 열은 '.' 로만 채워져있다. 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 연결할 수 있다. 놓을 수 있는 파이프의 최대값을 출력한다. 🔸 풀이 전략 🔸 R이 최대 1만, C가 최대 500이므로 효율적인 선택 방법이 필요하다.(그리디) 최대한 많은 파이프를 두기 위해서는 가능한 위쪽으..