기록방

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

👉 문제링크 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 🔸 문제 분석 🔸 문제 내용 N명의 사람과 M개의 파티가 있다. 진실을 아는 사람이 참여한 파티에서는 진실만 말해야 한다. 진실을 말한 파티에 있던 사람들도 진실을 아는 사람이 된다. 거짓을 말할 수 있는 파티의 수를 출력한다. 풀이 전략 같은 파티 참가자를 연결해야 한다. 각 파티별 참가자 List와 개인 별 참가 파티 List를 만든다. BFS로 진실을 말한 파티와 진실을 알게된 사람들을 추가해 나간다. 진실을 말하지 않은 파티의 수를 출력한다. 2024...

👉 문제링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🔸 문제 분석 🔸 N명의 학생들을 키 순서대로 줄을 세운다. 모두의 키 정보가 주어지는 것이 아니라, 두 학생을 비교해서 누가 앞에 오는지에 대한 정보만 주어진다. 위상 정렬 알고리즘에 대한 간단한 문제이다. 키가 큰 학생이 앞에 오는지, 작은 학생이 앞에 오는지에 대한 정보는 없고, 누가 앞으로 오느냐만 주어진다. 따라서 답이 여러가지가 될 수 있으므로 서브테스크 문제이다. BFS로 간단히 풀이할 수 있다..

👉 문제링크 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 🔸 문제 분석 🔸 육지는 상하좌우로 건널 수 있는 땅이다. 두 보물은 한 육지에 있으며, 최단 거리가 가장 긴 두 위치에 있다. bfs로 가장 멀리 퍼진곳을 찾으면, 최단 거리 중 가장 긴 거리이다. 두 보물 사이를 이동하는 시간을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Ar..

👉 문제링크 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 🔸 문제 분석 🔸 10 x 10 게임판에서 100개의 칸 중 첫 칸에서 마지막 칸 까지 가야한다. 주사위 값을 원하는 대로 던질 수 있다. 사다리를 만나면 연결 된 칸으로 내려가고, 뱀을 만나면 연결 된 칸으로 올라간다. 사다리와 뱀이 겹치거나 연속 된 곳은 없다. 주사위 경우의 수를 BFS로 모두 확인하며 도착하는 최단 경로를 구한다. 🔸 코드 🔸 import java.io.BufferedReader; ..