Doby's Lab

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/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 다익스트라로 하기엔 여러 번 함수 콜이 귀찮아서 플로이드로 한 번에 모든 최소 비용 경로를 구했다. (얼마나 귀찮았으면 플로이드도 짜놓고 콜 안 해서 틀렸을까^^) 1) 모든 최소 비용 경로를 구한다. 2) 1~n까지 돌며 방에 있는 사람들로부터 각 노드로 가는 최소 비용을 다 더 했을 때, 제일 작은 방을 출력한다. #include #include #include #define MAX 100 +..

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/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이번 문제의 어려운 점은 아마 "i에서 j로 갈 때의 최단 경로에 속한 노드들"을 구하는 것이었다. [시도 #1] 다익스트라에서 경로 역추적했던 것을 영감 삼아 해결해보려 했었다. 3차원 동적배열을 선언하여 i와 j에 k가 들어가면서 최단 경로가 갱신될 때마다 k를 push 했다. if (graph[i][k] + graph[k][j] < graph[i][j]) { graph[i][j] = gr..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 판단 실수로 플로이드 와샬 안에서도 최단 경로를 갱신할 때 m(수색 범위) 이내에 있는 것만 갱신해줬었다. 어쨌거나 최단 경로들은 모두 갱신한 후에 m(수색 범위) 안에서 갈 수 있는 길을 찾아야 하는 것이 포인트다. #include #include #define MAX 100 + 1 #define INF 987654321 using namespace std; int graph[MAX][MAX]; in..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 이번 문제의 핵심이 플로이드 와샬이긴 하지만 개인적인 느낌으로는 플로이드 와샬을 끝내고, 회장 후보 수와 회장 후보들을 출력하는 게 더 핵심처럼 와닿았다. 그래서 이번 문제는 '구현' 키워드에 넣어두었다. 왜냐하면 이런 식으로 최솟값을 구하고, 그 최솟값을 유발하는 인덱스 or 노드들을 처리하는 방법은 볼 때마다 헷갈렸었기에 이번 기회에 직접 구현해보았다. [구현] score가 나왔을 때, 그것이..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 또 똑같은 키워드다. (https://draw-code-boy.tistory.com/151) (https://draw-code-boy.tistory.com/153) 다만, 시간 초과가 나와서 ios_base::sync_with_stdio(false); cin.tie(NULL); 를 해주고, 값을 복사해주는 cache의 역할이 사실상 의미가 없기 때문에 graph에 입력받은 값을 복사하지 않..