전체 글

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구하는 문제입니다. 플로이드-워셜 알고리즘을 통해 문제를 해결하였습니다. 풀이 플로이드-워셜 플로이드-워셜 알고리즘은 모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구하는 문제입니다. 이 거리는 음수 가중치가 있더라도 동작하며 시간 복잡도는 $O(N^3)$으로 매우 큰 편입니다. 따라서 입력 정점이 작다는 특징도 있습니다. 플로이드 워셜은 다음과 같은 단계를 통해 값을 구해냅니다. 모든 도시에 대해서 ..

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 도시들과 도시들 사이에 지나는 버스 그리고 버스가 목적지 도시로 이동하는데 걸리는 시간이 주어졌을 때 최단 거리를 구하여라 단, 버스들은 음의 시간을 지나는 시간이 있을 수 있다. 즉, 시간을 거슬러올라가는 타임머신 버스가 있다. 풀이 해당 문제는 음의 가중치가 존재하기 때문에 다익스트라로는 해결할 수 없고 벨만-포드 알고리즘을 통해 풀어야 합니다. 벨만-포드 알고리즘 벨만-포드 알고리즘은 전체 노..

1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 도시들이 주어지고 도시들을 연결해주는 버스가 주어졌을 때 출발지 도시에서 목적지 도시까지의 최단 거리를 구하여라. 풀이 최적화된 다익스트라 알고리즘 설명 [JAVA] 백준 1753 다익스트라 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 g-..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어졌을 때 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 풀이 하나의 출발점에서 다른 모든 노드로 향하는 최단 거리를 구하라는 문제이기 때문에 다익스트라 알고리즘을 사용하여 풀었습니다. 📌 입력 boolean[] V = new boolean[N]; ArrayList[]A = new ArrayList[N]; int[] distance = new int[N]; for(int i=1..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 여러개의 건물이 있을 때 각 건물은 다른 건물이 지어져야 하는 요구사항이 있다. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다. 풀이 이 문제는 건물이 앞에있는 건물들이 지어졌을 때, 지을 수 있는 건물들이 있다. 따라서 위상정렬을 통해 노드들을 제거해나가면서 시간을 계산하면 된다. 📌 입력 ArrayList[] A = new ArrayList[N]; int[] D = new int[N]; int[] time = new int[N];..

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 풀이 1번 학생이 3번학생보다 먼저 앞에 서야한다. 이런 식으로 값이 주어지기 때문에 1번 학생을 먼저 출력하고 3번학생을 출력한다. 즉, 위상정렬과 일치한다. 그리고 답이 여러가지라는 의미도 위상정렬을 의미한다. 📌 입력 for(int i=0; i

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 여러 파티에 참여할 때 진실을 알고 있는 사람과 진실을 알고있는 사람과 파티를 하는 사람을 피해 과장된 이야기를 할 수 있는 파티의 최대 수를 구하여라. 풀이 📌 유니온 파인드 static void union(int a, int b){ int x = find(a); int y = find(b); A[y] = x; } static int find(int a){ if(A[a] == a){ return a; }else{ A[a] = find(A[a]); return A[a..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 도시의 개수가 주어지고 각 도시들이 연결되어 있는지 여부가 주여졌을 때 가려고 하는 여행지를 모두 갈 수 있는지 여부를 출력하시오. 풀이 📌 유니온 파인드 static void union(int a, int b){ int x = find(a); int y = find(b); A[y] = x; } static int find(int a){ if(A[a] == a){ return a; }else{ A[a] = find(A[a]); return A[a]; } }..