https://www.acmicpc.net/problem/2645 2645번: 회로배치 회로를 n×n의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 가장자리에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자 www.acmicpc.net 이미 회로가 놓인 위치를 2차원 배열에 표시해 놓고, 다익스트라 알고리즘을 통해 시작 지점부터 도착 지점까지 도달하는데 최소비용을 계산했다. 이때 최소비용을 계산하면서, come_from[55][55] 에 해당 위치로 오기 전에 직전에 어떤 위치에 있었는지 저장해 놓고, 도착 지점까지 최소 비용 계산이 끝나면 come_from[55][55]을 이용해 도착지점부터 시작지점까지 거꾸로 확인하면서 ..

https://www.acmicpc.net/problem/1432 1432번: 그래프 수정 첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접행렬 형식으로 입력이 주어진다. 0은 연결되지 않았음을 의미하고, 1은 연결되었다는 것을 의미한다. N은 50보다 작거나 같은 www.acmicpc.net 플로이드 와샬을 통해 그래프의 사이클이 존재하는지 확인하였고, 위상 정렬을 이용해서 정점의 번호를 매기는 방법을 통해 문제를 해결했다. 이때 주의해야 될 점은, 그래프 간선의 방향을 거꾸로 하여 위상 정렬을 수행하면서 우선순위 큐에서 정점의 번호가 큰 것부터 나오게 하여 정점의 번호가 큰 정점부터 새로운 큰 번호를 부여해 나아가는 방식으로 문제를 해결해야 한다. 왜냐하면 그래프의 방향을 거꾸로..

https://www.acmicpc.net/problem/1412 1412번: 일방통행 첫째 줄에 도시의 개수 N(2 ≤ N ≤ 50) 이 주어진다. 둘째 줄부터 N개의 줄에 도로의 정보가 주어진다. 인접행렬처럼 주어진다. i행 j열이 의미하는 정보는 Y 또는 N인데, Y일 때는 i에서 j으로 가는 www.acmicpc.net 사이클의 존재를 확인하는데, 양방향 도로는 단방향 도로로 만들 수 있어서 양방향 도로가 속해있는 사이클은 사이클이 존재하지 않도록 만들 수 있으므로, 단방향 도로로만 이루어진 그래프에서 사이클이 존재하는지만 확인하는 방법으로 문제를 해결했다. 단방향 도로로만 이루어진 그래프에서 사이클의 존재를 확인하는 방법은 플로이드 와샬을 이용해서 확인했다. 코드 #include #include..

https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net k명의 학생을 고르는 경우를 확인하여 문제를 해결했는데, 해당 학생을 고를지 확인할 때 지금까지 고른 학생들과 모두 친구 관계인지 확인하는 방법을 통해 확인했다. 이를 위해 이전에 friend_check[A][B]에 A학생과 B학생이 친구 관계인지 정보를 저장해 놓았다. 코드 #include #include #include using namespace std; int k, n, f; int friend..

https://www.acmicpc.net/problem/12012 12012번: Closing the Farm (Gold) The output consists of \(N\) lines, each containing "YES" or "NO". The first line indicates whether the initial farm is fully connected, and line \(i+1\) indicates whether the farm is fully connected after the \(i\)th closing. www.acmicpc.net 농장을 닫히는 순서대로 닫는 게 아니라, 농장이 닫히는 순서로 거꾸로 하여 모든 농장이 닫힌 상태(끊어진 상태)에서 농장을 하나씩 추가하여 연결하는 오프..

https://www.acmicpc.net/problem/9571 9571번: Crowded Cows Farmer John's N cows (1 xi >> hi; cow.push_back(make_pair(xi, hi)); } sort(cow.begin(), cow.end()); cow.push_back(make_pair(2000000005, 2000000005)); MakeSgmtt(0, 0, n - 1); int check_left_index = 0; int check_right_index = 0; for (int i = 0; i < n; i++) { //붐비는 소인지 확인할 소 int here = cow[i].first; int here_height = cow[i].second; //현재 위치의 왼..