기록방

👉 문제링크 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 🔸 문제 분석 🔸 N개의 노드와 E개의 간선이 있다. 1번 노드부터 N번 노드까지의 최단거리를 구하는데 v1과 v2 노드를 경유해야 한다. 다익스트라 알고리즘의 활용으로 풀이 가능하다. (난 프림 알고리즘으로 생각했다) 경로는 2가지 종류가 있다. (1 > A > B > N , 1 > B > A > N) 첫 번째 경우는 1 > A, A > B, B > N 의 최단거리를 각각 구해야 한다. 두 번째 경우는 ..

👉 문제링크 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 🔸 문제 분석 🔸 N명의 사람과 M개의 도로가 있다. X번 사람의 집에 모두가 최단거리로 모이고 집에 갈 때, 소요시간의 최대 값을 출력한다. 각 집 사이의 도로는 단방향 연결이다. 최단거리를 구하고 그 중 최대 값을 찾아야 한다. 각자 집에서 파티로 갈 때는 각각의 최단 거리를 구해야 하므로, 다익스트라 알고리즘을 N-1번 반복한다. 파티에서 집으로 돌아갈 때는 시작 노드에서 다른 모든 노드로의 최단 거리를 구해야 하..

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

👉 문제링크 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🔸 문제 분석 🔸 N개의 자연수 중 M개를 고른 수열을 모두 구한다. 수열은 중복되선 안되며 사전 순으로 증가하는 순서로 출력한다. N개의 자연수는 중복이 있을 수 있다. 순열로 M개의 원소를 고르고, 중복을 제거하면 된다. 🔸 코드 🔸 import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public cla..

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