Doby's Lab

https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 다익스트라 문제였으나 조금 더 디테일한 조건 분기가 필요했다. if(canHide[next] && next != n - 1) continue; 적에게 들킬 경우 가지 말고, 하지만 넥서스라면 갈 수 있게끔 조건이 필요했다. 그리고, 최댓값의 경우 10,000,000,000가 나오니까 INF를 987654321이 아닌 더 큰 수가 필요하고, int 형의 범위를 넘어서기 때..

https://www.acmicpc.net/problem/5590 5590번: 船旅 入力の 1 行目には2つの整数 n, k (1 ≦ n ≦ 100, 1 ≦ k ≦ 5000) が書かれている． これは，島の数が n 島で，入力が k + 1 行からなることを表す． i + 1 行目 (1 ≦ i ≦ k) には， 3 個または 4 個の www.acmicpc.net 파파고 돌려서 번역했다. 다익스트라 문제였다. 0 b c: b에서 c로 가는 최단 경로를 구하라. 갈 수 없다면 -1 1 b c d: 는 b와 c를 이어주는 가중치가 d인 양방향 경로가 생긴다. [AC 코드] #include #include #include #include #define pii pair #define MAX (100 + 1) #define INF ..

https://www.acmicpc.net/problem/12834 12834번: 주간 미팅 첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000) 둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V) 셋째 줄에 팀원 N명의 www.acmicpc.net 간단한 다익스트라 문제다. 갈 수 없는 길이 나올 땐 -1 처리를 해주고, 모든 최단 경로를 더한 값을 출력하면 된다. #include #include #include #include #define MAX 1000 + 1 #define INF 987654321 #define pii pair using namespace std; vec..

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 1) 위험한 구역은 1을 대입, 죽음의 구역은 2를 대입 2) 다익스트라를 돌려 2가 나오면 continue 시킴 3) x1, y1, x2, y2를 입력받으면 x1 > x2 혹은 y1 > y2일 때 둘을 swap 시키는 작업을 해주었음 4) 다익스트라를 돌리고 나서 (500, 500)이 INF라면 -1 출력 아니라면 최소 비용 출력 #include #include #inclu..

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 이번 문제는 문제의 뜻을 파악하기가 어렵다. (https://yabmoons.tistory.com/444) 우선 최소 몇 개의 회선을 복구해야 하는지는 당연히 1부터 2 ~ N까지 가는 회선의 최소 개수이기 때문에 K = N - 1이다. 1은 슈퍼 컴퓨터이므로 1을 제외한 각 노드들로부터 1로 가는 제일 첫 노드로 가는 간선을 출력해주면 된다. #include #incl..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net [솔루션] 1) 벽 한 번 부술 때, 비용을 1로 처리한다. 2) 다익스트라를 돌려서 n행 n열까지 가는 데에 벽을 부순 최소 횟수를 구한다. (다익스트라 이용) +) 모든 가중치가 1이라 BFS로도 풀릴 거 같다. #include #include #include #include #define MAX 50 + 1 #define INF 987654321 #define pii pair using na..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제를 읽고, 그래프가 양방향 그래프인 것을 알고 다익스트라를 돌리면 된다. #include #include #include #include #define MAX 50000 + 1 #define INF 987654321 #define pii pair using namespace std; int n, m; vector graph[MAX]; int dist[MAX]; struct cmp { bool opera..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제 또한 다익스트라를 통해 최소 비용을 구하고, 다익스트라에서 경로 역추적을 하여 최소 비용을 발생시키는 노드들의 배열을 담아서 main에서 이 노드들을 while을 통해 result배열에 담아 출력해주면 되는 간단한 문제였다. 하지만, 주어진 예제와 내 답이 달라서 틀린 건가 싶었지만 직접 그림을 그려보니 내 답도 만족하는 경우라서 혹시나 하는 마음에 제출을..