일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 컴퓨터공학 #자료구조 #스택 #c++ #알고리즘 #백준문제풀이
- HTML #CSS
- 컴퓨터공학 #c #c언어 #문자열입력
- 컴퓨터공학 #Java #자바 #클래스 #객체 #인스턴스
- 잔
- BOJ #컴퓨터공학 #C++ #알고리즘 #자료구조
- Today
- Total
영벨롭 개발 일지
[백준 BOJ][C++]14889번 스타트와 링크 풀이: DFS 본문
https://www.acmicpc.net/problem/14889
이 문제는 DFS로 해결할 수 있습니다.
먼저 0~n-1의 index 중 n/2 길이의 조합을 탐색합니다.
n = 4 일 때 0, 1, 2, 3 중 길이 2의 순열은
(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) 총 6가지가 됩니다.
(0, 1) 을 기준으로 계산을 한다고 가정하면,
우리는 s[0][1] + s[1][0] 과 s[2][3] + s[3][2] 의 차이를 계산해야하겠죠?
그렇다면 (2, 3)을 기준으로 계산 했을 때와 중복되는 계산을 하게 됩니다.
때문에 중복 계산을 막기 위해 우리는 (0, 1), (0, 2), (0, 3) 기준으로만 계산을 해야하겠죠!
0, 1, 2, 3 부터 시작하여 모두 dfs를 실행하면 위 6가지의 순열이 모두 탐색되지만 0부터 시작한 dfs 만 실행하면 우리가 원하는 조합을 뽑을 수 있습니다.
m=n/2 길이의 조합을 뽑기 위해선 dfs에서 다음 탐색할 index 번호의 조건으로 (n-1-i) >= (m-1-depth) 를 줘야합니다.
n-1 : 숫자 배열의 마지막 index
i : 탐색할 번호의 index
n-1 - i : 탐색할 번호 다음에 남은 수들의 개수
m - 1 - depth : 현재 depth 다음 depth에서 앞으로 추가해야할 수들의 개수 ( m = n/2 )
arr에 m 길이의 원소가 추가 되고 나면 추가되지 않은 index 들을 arr에 추가한 뒤 calculation을 호출하여 스타트팀(0~m-1까지의 index)과 링크팀(m~n까지의 index)의 합의 차를 반환 받습니다.
이 반환값을 ans와 비교하여 더 작은 값을 ans에 저장하면 됩니다.
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int n;
int ans = 1000000000;
int s[21][21];
int arr[21];
bool visit[21] = { false, };
int calculation(int m) {
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < m; i++) {
int x = arr[i];
for (int j = 0; j < m; j++) {
if (i == j)
continue;
int y = arr[j];
sum1 += s[x][y];
}
}
for (int i = m; i < n; i++) {
int x = arr[i];
for (int j = m; j < n; j++) {
if (i == j)
continue;
int y = arr[j];
sum2 += s[x][y];
}
}
return abs(sum1 - sum2);
}
void dfs(int idx, int depth) {
int m = n / 2;
if (depth == m) {
for (int i = 0; i < n; i++) {
if (!visit[i])
arr[depth++] = i;
}
ans = min(ans, calculation(m));
return;
}
for (int i = idx + 1; i < n; i++) {
if (!visit[i] && (n - 1 - i) >= (m - 1 - depth)) {
visit[i] = true;
arr[depth] = i;
dfs(i, depth + 1);
visit[i] = false;
}
}
}
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cin >> s[i][j];
}
arr[0] = 0;
visit[0] = true;
dfs(0, 1);
cout << ans;
return 0;
}
'알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글
[백준 BOJ][C++]1759번 암호 만들기 풀이: DFS (0) | 2022.04.06 |
---|---|
[백준 BOJ][C++]2210번 숫자판 점프 풀이: DFS (0) | 2022.04.06 |
[백준 BOJ][C++]6603번 로또 풀이: DFS (0) | 2022.04.05 |
[백준 BOJ][C++]10971번 원판원 순회2 풀이: DFS or next_permutation() (0) | 2022.04.01 |
[백준 BOJ][C++]9375번 패션왕 신해빈 풀이: hash (0) | 2022.03.31 |