L.O.K

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net ◎ 문제풀이 사건의 전후관계라는 말에서 Floyd-Warshall 알고리즘을 떠올릴 수 있어야 한다. Floyd-Warshall은 A->B를 가고 B->C를 갈 수 있으면 A->C를 갈 수 있다는 원리를 적용하여 최단경로를 구하는 알고리즘이다. A사건 후 B사건이 발생하고 B사건 후 C사건이 발생하면 A사건 후 C사건이 발생한다. 이것이 성립한다면 B사건 전 A사건이 발생하고 C사건 전 B사건이 발생하면 C사건 전 A사건이 발생함을 의미하기도 한다. 이런..

10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net ◎ 문제풀이 ( 1의 무게 ) > ( 4의 무게 ) 이고 ( 4의 무게 ) > ( 3의 무게 ) 이면 ( 1의 무게 ) > ( 4의 무게 ) > ( 3의 무게 ) 가 성립된다. 위 관계가 성립되지 않는 것의 개수를 구해야 한다. 1,2,3,4 .. 를 노드로 보고 크고 작음의 관계를 간선으로 한다면 그래프를 떠올릴 수 있다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란? [Algorithm] 다익스트라 알고..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ◎ 문제풀이 가장 기본적인 플로이드-워셜 알고리즘 문제이다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란? [Algorithm] 다익스트라 알고리즘(Dijkstra)이란? 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 다른지점으로 가는 최단경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 그 lordofkangs.tistory.com 알고리..

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ◎ 문제풀이 다익스트라 알고리즘 문제로 알려져 있는데, 문제를 보니 플로이드 워셜 알고리즘이 더 어울린다고 생각했다. 시작점이 정해져 있지 않았고 모든 노드를 기준으로 하기 때문이다. 플로이드 워셜은 삼중for문을 구현하므로 시간초과를 조심해야 하는데, 시간제한이 1초이고 n이 1000이하라 삼중for문을 돌리면 얼추 시간초과가 걸리지 않는다고 생각했다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란?..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net ◎ 문제풀이 노드와 노드를 이동하는데 최단거리를 구하는 문제이다. 비용이 동일하면 BFS 알고리즘이 적절하지만 노드와 노드 사이의 비용이 상이하므로 최단경로를 구하는 알고리즘을 사용해야 한다. 특정한 시작점이 주어지고 모든 간선의 비용이 양수라면 다익스트라 알고리즘으로 최단경로를 계산한다. [Algorithm] 다익스트라 알고리즘(Dijkstra)이란? 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 ..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ◎문제풀이 무방향 그래프의 연결요소의 개수를 구하는 문제이다. 연결요소는 끊어짐 없이 연결된 그래프를 의미한다. 무방향 그래프에서 연결요소를 구하는 대표적인 알고리즘은 UNION-FIND 알고리즘이다. [Algorithm] Union-Find 알고리즘이란? ( with 서로소 집합 자료구조 ) 서로소 집합(Disjoint Sets)이란? 공통원소가 없는 두 집합을 의미한다. 이는 그래프(Graph) 구..

◎ 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주..

◎ 문제 공중미래도시는 1번부터 N번까지 회사가 있으며 서로 도로로 연결되어 있다. 방문판매원A는 현재 1번에 있으며 X번 회사에 방문하여 물건을 판매하려고 한다. 연결된 2개의 회사는 양방향 이동이 가능하다. 회사와 회사를 연결하는 도로는 마하의 속도로 사람을 이동시켜 모두 정확히 1만큼의 시간으로 이동한다. 또한 방문판매원A는 소개팅에도 참석하려고 한다. 소캐팅 상대는 K번회사에 있다. 방문판매원A는 K번회사에 참석한 뒤 X번 회사로 가는 것이 목표다. 방문판매원이 회사 사이를 이동하는 최소시간을 계산하는 프로그램을 작성하시오. - 입력조건 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다.(1