mojo's Blog

문제 링크 : 2611번: 자동차경주 (acmicpc.net) 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net 문제 자동차 경주로는 의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다. 자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없..

문제 링크 => 11404번: 플로이드 (acmicpc.net) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Floyd-warshall 알고리즘을 이용한 문제이다. 문제 풀이순서는 다음과 같다. (d[x][y] = x에서 y까지 이동할 수 있는 최단 경로) 1. d[x][y] 의 값을 미리 세팅한다. (1) x = y 일 경우 : d[x][y] = 0 (자기 자신으로 가는 경우는 0) (2) x ≠ y 일 경우 : d[x][y] = INF (이동할 수 없는 경우를 INF 으로 마킹) 2. 인풋으로 주어진 x..

문제 링크 => 11779번: 최소비용 구하기 2 (acmicpc.net) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 전형적인 다익스트라 문제이다. 다익스트라 알고리즘을 활용하여 최소거리를 구할 수 있어야 하며 동시에 경로까지 출력해야 하는 문제이다. 경로를 추적하기 위한 배열 trace 를 이용하였다. 시작 지점으로부터 다음 지점(next)까지의 최소 거리를 Distance[next] 라고 할 때 해당 값이 update 될 때마다 현재 위치(cur)에 대해서 trace[n..

문제 링크 => 23743번: 방탈출 (acmicpc.net) 23743번: 방탈출 첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으 www.acmicpc.net 방탈출 카페에는 1번부터 N번까지 총 N개의 방이 있고, 각 방에는 친구들이 한 명씩 들어가 있다. 모든 방은 외부로부터 완전히 독립되어 있다. 방에서 탈출하지 못하는 친구들이 답답했던 원빈이는 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하려고 한다. 워프는 최대 M개까지 설치할 수 있는데, i번째 워프는 ..

문제 링크 => 11378번: 열혈강호 4 (acmicpc.net) 11378번: 열혈강호 4 첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 www.acmicpc.net 최대 유량 문제이다. 이 문제는 열혈강호 3 문제에서 약간의 변형이 이루어진 문제이다. 열혈강호 3 문제에서는 K 명은 최대 일을 2개 할 수 있다고 되어있다. 그러나 열혈강호 4 문제에서는 K 명이 동일하게 일을 2개 할 수 있거나 한명에게 몰빵하여 최대 (K + 1)개를 할 수 있다는 점에 있다. 이를 에드몬드-카프 알고리즘을 활용하여 다음과 같이 간선을 ..

문제 링크 => 2056번: 작업 (acmicpc.net) 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬 + 다이나믹 프로그래밍 문제이다. 먼저 작업들 간의 inDegree를 설정해야 한다. 즉, inDegree[x] = 0 인 경우에 다음 작업으로의 진행이 가능하고 그 다음 작업을 완료하기 위한 최소 시간을 정해야 한다. 위 그림과 같이 x1, x2, ..., xi를 현재 처리한 작업들이고 next를 그 다음 작업이라고 하자. 현재까지 작업을 완료하기 위한 최소 시간을 R(x) 라고 해보..