개발하는 고라니

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [다익스트라] 입력으로 출발 정점과 도착 정점이 주어지므로 한 정점에서 모든 정점으로의 최단 거리를 구하면 된다. 이 문제는 무난한 다익스트라 문제같이 보이나, 출발 정점 ~ 도착 정점 최단 거리의 경로를 구해야 한다. 나는 이 과정을 Dijkstra() 내에서 구현하였다. int[] from 라는 배열에 다음 정점을 방문하기 전에 어디서 왔는지에 대한 정보를 적었다. ( from[next] = current ) 아무튼 이건 포스팅..

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [플로이드-와샬] 일반적인 플로이드-와샬을 이용하여 모든 사람간의 키 순서를 구하면 된다. 여기까지는 유추하기 쉬울 수 있으나, 특정 사람 i가 몇 번째로 큰 것 인지에 대한 것을 판단하기는 약간 어려울 수 있다. 만일 특정 사람 i가 다른 사람 j에 대하여 키 관계를 모를 때, j 입장에서도 i의 키 관계를 모른다면 그것은 자신이 몇 번째로 큰 사람인지 모르는 것과 마찬가지이다. # Code import java.io.BufferedReader; import j..

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net [플로이드-와샬 (Floyd-Warshall) 알고리즘] 이 문제를 풀기위해 플로이드 와샬 알고리즘을 공부했다. 이 문제를 DFS만으로 풀려고 하니까 TC에서 헤어나오질 못하였다. 사실 당연하다. 최대 정점의 수는 500개이나, 이후 최대 50,000개의 사건이 주어지므로, DFS 1번 당 최대 50,000 재귀를 한다고 할 때, 25,000,000번 호출되지 않을까? 하는 생각이 들었다. 역시 어떻게 풀어야할지 몰라 무식하게 접근한 꼴이다. 플로이드 와..

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net # 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다...

최단 경로 최단 경로 문제에서 입력 그래프의 유형은 크게 두 가지이다. 모든 간선 가중치가 음이 아닌 경우 음의 가중치가 존재하는 경우 음의 가중치를 허용하지 않는 경우 다익스트라(Dijkstra) 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치를 허용하는 경우 벨만-포드 알고리즘으로 이 유형의 문제를 푼다. 음의 가중치는 허용하지만 가중치 합이 음수인 사이클은 절대 허용하지 않는다. 음의 사이클이 있으면 해당 사이클을 몇번이고 돌아 경로의 가중치 합을 무한정 낮출 수 있기 때문에 최단 경로 문제 자체가 성립하지 않는다. Dijkstra 알고리즘 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구한다. 다만 이 때 음의 가중치를 갖는 간선은 허용하지 않는다. 임의의 두 정점 ..