-
2024 - 10- 24 C++ 코딩테스트 10주완성 D+50카테고리 없음 2024. 10. 25. 15:20
백준 17471 문제 - 게리맨더링
백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다.
견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다.
이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다.
구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다.
선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.
아래는 백준시를 두 선거구로 나눈 4가지 방법이며, 가능한 방법과 불가능한 방법에 대한 예시이다.
공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다.
백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.
입력
첫째 줄에 구역의 개수 N이 주어진다.
둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다.
(인구는 공백으로 구분되어져 있다.)
셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다.
(각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.)
구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다.(인접한 구역이 없을 수도 있다.)출력
첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다.
두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.#include <bits/stdc++.h> using namespace std; const int INF = 987654321; int n, a[11], m, temp, ret = INF, comp[11], visited[11]; vector<int> adj[11]; pair<int, int> dfs(int here, int value){ visited[here] = 1; pair<int, int> ret = {1, a[here]}; for(int there : adj[here]){ if(comp[there] != value) continue; if(visited[there]) continue; pair<int, int> _temp = dfs(there, value); ret.first += _temp.first; ret.second += _temp.second; } return ret; } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ cin >> m; for(int j = 0; j < m; j++){ cin >> temp; adj[i].push_back(temp); adj[temp].push_back(i); } //양방향 간선을 입력받음. } //i는 2^구역의 개수 -1 을 하면 모든 경우의수 for(int i = 1; i < (1 << n) - 1; i++){ fill(comp, comp + 11, 0); fill(visited, visited + 11, 0); int idx1 = -1, idx2 = -1; //구역의 수만큼 반복문 for(int j = 0; j < n; j++){ if(i & (1 << j)){comp[j + 1] = 1; idx1 = j + 1;} else idx2 = j + 1; } pair<int, int> comp1 = dfs(idx1, 1); pair<int, int> comp2 = dfs(idx2, 0); //first 의 합이 n이 되는 경우는 모든 탐색을 했다는 것이므로.. if(comp1.first + comp2.first == n) ret = min(ret, abs(comp1.second - comp2.second)); } cout << (ret == INF ? -1 : ret)<< "\n"; }아직 비트마스킹 연산자들이 익숙하지 않아 이해하는데 쉽지않았지만 그래도 계속 코드를 들여다보니 어느정도 숙지가 되었다..!!!
이 문제의 핵심로직은 구역의 모든 경우의 수에서 dfs 탐색을 두개로 쪼개어 선거구를 두개로 쪼개어 탐색하는 것이다!
그 다음, 두개의 dfs 탐색이 끝난 뒤에 각각의 탐색을 한 횟수를 더하여 N 이 나올 시 모든 탐색을 끝마친 것이므로
두개의 선거구를 빼서 결과값과 비교하여준뒤,더 작은 수를 저장하여준다.
이 코드의 실행순서를 보자!
1.구역의 개수를 N을 입력받는다.
2.구역의 개수만큼 반복문을 돌린다.
ㄴ2-1. 각 구역 i 에 연결된 구역의 개수 m을 입력받는다.
ㄴ2-2. m만큼 각 구역에 연결된 구역의 수를 push_back 하여주고, 서로 연결된 것이므로 반대로도 push_back하여준다.
3.모든 경우의 수 (1 << n) -1 만큼 반복문을 돌린다.
ㄴ 3-1. 구역의 수만큼 반복문을 돌린다.
ㄴ 3-2. 현재 경우의 수에 해당하는 비트가 나올시 comp[j +1] = 1; 을 하여 해당 인덱스에 값을 대입해준다.
첫번째 선거구를 탐색하게 되는 위치 idx1 = j+1 을 하여준다.
마지막 조건을 만족하는 j+1이 들어가므로 첫번째 선거구의 마지막 인덱스값이 들어가게된다.
ㄴ 3-3. 아닐 경우 두번째 선거구를 탐색하게 되는 위치 idx2 = j +1 하여준다.
ㄴ 3-4. dfs(idx1,0) 과 dfs(idx2,0) 를 순서대로 돌려준다.
ㄴ 3-4 pair<int,int> dfs(int here, int value)
ㄴ 3-4-1. 방문배열을 visited[here] = 1을 하여 방문한 위치를 표시해준다.
ㄴ 3-4-2. 현재의 구역의 인구값인 a[here]을 할당한 내부변수 pair<int,int> ret을 선언해준다.
ㄴ 3-4-3. int there : adj[here] adj의 here 안에 연결된 구역을 반복문
ㄴ 3-4-3-1. 만약 comp[there] 의 값이 value가 아닐 경우 해당 선거구를 탐색하는 것이 아니므로 continue ㄴ 3-4-3-2. visited[there]의 값이 있을 경우 해당 구역을 방문했다는 것이므로 continue
ㄴ 3-4-3-3. dfs(there, value)를 호출시켜주어 해당 구역에서 연결된 다른 구역으로 탐색을 시켜준다.
ㄴ 3-4-3-4. ret.first += _temp.first; 해당 선거구 구역을 몇개 탐색하였는지 알기위한 코드이다.
ㄴ 3-4-3-5. ret.second += ret.second; 해당 선거구의 각 구역당 인구수 총합을 구하기 위한 코드이다.
ㄴ 3-5. 두개의 dfs 탐색이 끝나면 pair<int,int> 로 comp1,comp2로 각각 반환받는다.
ㄴ 3-6. 반환받은 comp1.first 와 comp2.first의 값이 n과 같을 경우 모든 구역을 탐색한 것이므로 선거구는 두개이므로 인구의 최솟값인 ret 과 abs(comp1.second - comp2.second) 를 비교하여 더 작은 수를 저장해준다.
4. ret이 초기값이 아니라면 ret을 출력시켜주고 초기값일시 -1 을 출력시켜준다.모든 경우의 수는 그렇다치더라도
선거구를 두개로 나누어 계산하는 것
각각의 탐색의 구역의 수를 더하여서 n이 나올시 선거구가 두개 라는 생각을 못했다..!
배워야할점이 아직 너무 많다.
백준 1987 문제 - 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데,
(새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.)
즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.
(말이 지나는 칸은 좌측 상단의 칸도 포함된다.)
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다 (1 <= R,C <= 20)
둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
실습코드
#include <iostream> #include <algorithm> using namespace std; int R, C, ret, ny, nx; char a[21][21]; const int dy[] = {-1, 0, 1, 0}; const int dx[] = { 0, 1, 0, -1}; void go(int y, int x, int num, int cnt){ ret = max(ret, cnt); for(int i = 0; i < 4; i++){ ny = y + dy[i], nx = x + dx[i]; if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue; int _next = (1 << (int)(a[ny][nx] - 'A')); if((num & _next) == 0) go(ny, nx, num | _next, cnt + 1); } return; } int main(){ cin >> R >> C; for(int i = 0; i < R; i++){ for(int j = 0; j < C; j++){ cin >> a[i][j]; } } go(0, 0, 1 << (int)(a[0][0] - 'A'), 1); cout << ret << '\n'; return 0; }저번 주차 DFS 탐색을 이용하여 한번 풀었던 적이 있는 문제이다.
이번 문제의 핵심로직은 visited 배열을 쓰지 않고도 비트마스킹을 이용하여 최댓값을 구하는 것이다!
이 코드의 실행순서를 확인해보자!
1. 행과 열의 개수를 입력받는다.
2. 행과 열의 개수만큼 반복문을 돌리고 해당 인덱스에 사용자 입력값을 집어넣어준다.
3. 시작위치가 0,0에서 시작해야한다고 했으므로 void go(int y, int x, int num, int cnt) 의 매개변수를 가진 함수에
y = 0, x=0을 넣어주고 num 에는 (int)(a[0][0] - 'A') 에 해당하는 수를 넣어준다. 그리고 시작위치이므로 cnt = 1을 대입해서 호출시켜준다.
ㄴ 3-1. 현재 cnt 와 ret을 비교하여 큰값을 저장시켜준다.
ㄴ 3-2. i =0 부터 4까지 반복문을 시켜준다.
ㄴ 3-1-1. ny = y + dy[i] 와 nx = x + dx[i] 를 해주어 호출된 y,x 위치에서 상하좌우의 위치값을 저장한다.
ㄴ 3-1-2. 만약 ny와 nx가 0 이하 또는 R 과 C의 값이되면
행과 열의 최대 최소범위를 벗어나는 것이므로 continue
ㄴ 3-1-3. 이를 통과할시 1 << (int)(a[ny][nx] - 'A') 값을 임시변수 _next 에 대입한다.
ㄴ 3-1-4. 만약 현재 num & _next 를 하여 0이 나올 시, 겹치는 문자가 없는 것이므로 재귀함수를 호출시켜준다.
ㄴ 3-1-4-1. go(ny,nx,num | _next, cnt +1) ny nx 위치로 넘어갈 시,
해당 a[ny][nx] 의 비트값을 num 안에 추가해야 하므로 num | _next 으로 매개변수를 전달하고
탐색을 한번 했으므로 현재 cnt에 +1을 하여 호출한다.
ㄴ3-3. 여기까지 넘어오면 탐색이 끝난것 또는 조건에 맞지않은것이므로 return
4. 최댓값을 저장한 ret을 출력시켜준다.처음 비트마스킹을 배울때 "아하 이렇게도 쓸 수 있구나.." 라고 생각했던 부분인데
막상 실습문제에서 나오니 바로 생각나질 않았다..ㅠ
이 실습문제를 연습삼아 보면 바로 떠오를 수 있게 복습하여야겠다.
백준 14890 문제 - 경사로
크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다.
길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
다음과 같은 N=6인 경우 지도를 살펴보자.
이때, 길은 총 2N개가 있으며, 아래와 같다.
길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다.
또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.
경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다.
경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
- 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
- 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
- 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
아래와 같은 경우에는 경사로를 놓을 수 없다.
- 경사로를 놓은 곳에 또 경사로를 놓는 경우
- 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
- 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
- 경사로를 놓다가 범위를 벗어나는 경우
L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.
경사로를 놓을 수 없는 경우는 아래와 같다.
위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.
가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.
지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다.
둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.출력
첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.
실습코드
#include <bits/stdc++.h> using namespace std; //변수목록 //지도의 행과열의 길이를 받을 정수형 변수 n //경사로의 길이의 정보를 입력받을 정수형 변수 L //지도의 정보를 입력받을 정수형 2차원 행렬 a //길의 개수를 카운트할 정수형 변수 cnt int n,L,a[104][104],cnt; int main() { cin >> n >> L; for(int i =0; i < n; i++) { for(int j =0; j < n; j++) cin >> a[i][j]; } //숫자가 같은경우 k-1 해서 호출 //숫자가 작은경우 현재 k값이 <0이면 k -1 해서 넘겨주어 호출 //숫자가 클경우 k < 0 작으면 원래 k값을 넣어주고 호출 k > 0 클 경우에는 리턴 for(int i=0; i < n; i++) { int K = L -1; for(int j =0; j < n-1; j++) { int abs_a = abs(a[i][j] - a[i][j+1]); if(a[i][j] == a[i][j +1]) K = K-1; else if(a[i][j] < a[i][j+1] && abs_a == 1) { if(K <= 0) K = L-1; else break; } else if(a[i][j] > a[i][j+1] && abs_a == 1) { if(K == L -1 || K <= 0) K = L -1; else break; } if(j == n-2) cnt++; } } for(int i =0; i < n; i++) { int K = L -1; for(int j =0; j < n-1; j++) { int abs_a = abs(a[j][i] - a[j+1][i]); if(a[j][i] == a[j+1][i]) K = K-1; else if(a[j][i] < a[j+1][i] && abs_a == 1) { if(K <= 1) K = L-1; else break; } else if(a[j][i] > a[j+1][i] && abs_a == 1) { if(K == L -1 || K <= 0) K = L -1; else break; } if(j == n-2) cnt++; } } cout << cnt; }L 이 2인경우에... 오류가 생기는 것같다.. 어떻게 해야할까
강의실습코드를 보자!
#include<bits/stdc++.h> using namespace std; int n, l, a[104][104], b[104][104], ret; void solve(int a[104][104]){ for(int i = 0; i < n; i++){ int cnt = 1; int j; for(j = 0; j < n - 1; j++){ if(a[i][j] == a[i][j + 1])cnt++; else if(a[i][j] + 1 == a[i][j + 1] && cnt >= l) cnt = 1; else if(a[i][j] - 1 == a[i][j + 1] && cnt >= 0) cnt = -l + 1; else break; } if(j == n - 1 && cnt >= 0) ret++; } return; } int main(){ scanf("%d %d", &n, &l); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ scanf("%d", &a[i][j]); b[j][i] = a[i][j]; } } solve(a); solve(b); printf("%d\n", ret); return 0; }이 문제의 핵심로직은 정수형 변수 cnt의 값을 이용하여서 경사면의 가능유무를 구별하는 것이다!
그리고 행과 열을 둘다 검사해야하는 것이므로, a의 지도의 정보를 입력받을때, i 와 j 값을 반대로 b의 지도에 대입하면
a의 대칭 즉 각 열의 값이 행에 입력되는 것이다.
이 두개의 행렬을 각각 검사하여 통과하는 줄마다 ret++를 하여주면 길의 개수를 도출할 수 있다.
이 코드의 실행순서를 살펴보자!
1. 지도의 길이와 경사면 최소길이의 값 N,L 을 입력받는다.
2. 지도의 정보를 입력받아 a[i][j] b[j][i] 에 각각 집어넣는다.
3.Solve(int a[104][104]) 함수안에 인자를 각각 a,b 넣어서 두번 호출시킨다. ( Solve(a); Solve(b);)
ㄴ 3-1. 지도의 길이 n까지 반복문
ㄴ 3-2. 이 반복문안에 j 와 j +1을 비교하는 코드가 있기떄문에 j=0 부터 n-1 까지 반복문
ㄴ 3-2.1. 만약 해당행렬의[i][j] 값과 [i][j+1] 값이 같을 경우, Cnt++
ㄴ 3-2-2. 만약 [i][j] 값과 [i][j+1] 값의 차이가 -1 이고, [i][j+1]의 값이 [i][j] 보다 큰 경우 이므로,
cnt의 값을 비교하여 L보다 클 경우에는 경사면의 최소길이를 만족했으므로 진행하고
cnt를 다시 1로 초기화
ㄴ 3-2-3. 만약 [i][j] 값과 [i][j+1] 값의 차이가 1 일경우,[i][j+1]의 값이 [i][j] 보다 작은 경우이므로,
cnt의 값을 비교하여 0이랑 같거나 작을 시, 이전 경사면의 조건을 충족한것 이므로, 진행하고
cnt를 -L + 1로 초기화
ㄴ 3-3. 반복문 정수 j의 값이 n-1이 됐을 경우, 마지막 원소까지 무사히 도착했다는 것이므로, 길의 조건을 만족하고 ret++
4. 길의 개수를 담은 ret을 출력시켜준다.Cnt를 이용한 로직은 나도 구성하였는데.. 음수로 쓰일줄은 몰랐다!
그리고 행렬을 대칭하여 쓴다는 방법은 상상하지도 못하였다..!! 나는 똑같은 반복문을 두번이나 썼는데..
오늘도 많이 배우고 간다!