[BOJ] 백준 15661 - 링크와 스타트 풀이
1. 문제
https://www.acmicpc.net/problem/15661
15661번: 링크와 스타트
첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100
www.acmicpc.net
2. 풀이
백준 실버 1에 해당하는 브루트포스 & 백트래킹 문제다.
알고리즘 스터디에서 발표할 때 이 문제를 들고 갔고 최적화 부분(재귀를 기존보다 덜 돌 수 있는 부분)에서 깨달음을 얻었다.
우리 스터디원들은 진짜 천재다...(나만 말하는 감자.....)
우선 이 문제의 해결 포인트로 생각한 건 백트래킹이었다.
팀원 수가 주어질 때 스타트팀과 링크팀을 나누는 것에서 백트래킹을 생각하여 접근하였다.
(글씨 쓰는 법 부터 연습해야 하나...)
백트래킹을 위한 visited[]을 선언해주는데, 이 vistied[]는 팀원을 어떻게 분배하는지를 나타낸다.
boolean 배열이므로 True : 스타트팀, False : 링크팀으로 설정해주면 true, false만으로 팀원을 나타낼 수 있다.
이를 알고 코드를 보면 setTeam()와 statsHap()가 있다.
setTeam()은 스타트팀원을 setting하는 함수이고 statsHap()는 능력치 합이 최소가 되는 것을 찾는 함수이다.
setTeam()에는 idx와 depth가 있는데, idx는 스타트 팀원을 고를 인덱스, depth는 스타트팀의 인원수를 나타낸다.
(1) 처음 main에서 0과 1을 넘겨주면 setTeam 함수에서는 N만큼 반복문을 돌면서 판단한다.
처음으로 판단하는 것은 지금 탐색하는 visited[i]가 true이냐이다. 이는 곧 스타트팀원이냐 링크팀원이냐를 묻는 것과 동일하다.
그 값을 true로 만들어주면 스타트팀원이 1명 있는 것이므로 처음 main에서 depth에 1을 넘겨준 것과 동일한 것이 된다.
다음 if문에서 스타트팀원의 수가 N / 2보다 크다는 것을 묻는다.
여기서 최적화 부분이 나오는데, 처음 문제를 풀었을 당시는 1명만 있어도 합의 최소를 구해야 하므로 1명 ~ 3명까지 총 재귀를 3번 돌면서 능력치 합이 최소가 되는 것을 찾았다.
그러나 잘 생각해보면 불필요한 호출이 있다는 것을 알 수 있다.
<N이 4일 때>
(1) 스타트팀원 : 1, 링크 팀원 : 3
(2) 스타트팀원 : 3, 링크 팀원 : 1
이 두 경우의 값은 어떨까? 같은 값이 나올 것이다.
왜냐하면 어느 팀이던 1명 팀이 나온 팀은 무조건 능력치 합이 0이 된다. 그리고 스타트 팀이 3명일 때와 링크 팀이 3명일 때는 탐색하는 인원의 인덱스가 나오는 경우의 수가 같으므로 결국 같은 값이 나오고, 이 차이는 결국 그 값이므로 같은 값이 되는 것이다.(이 부분에서 지적을 받았다.)
그렇다면 재귀를 1명 ~ 3명까지 도는 것이 아니라 2명까지만 돌면 최소 값이 구해진다는 결론이 나온다.
이 포인트를 잡고 depth(스타트팀 팀원) <= N / 2일 때 statsHap()을 실행한다.
(2) statsHap()에서는 능력치 배열을 2중 반복문을 돌면서 스타트 팀끼리 묶인 값을 계속 더해주고, 링크 팀끼리 묶인 값을 계속 더해준다.
그 후 마지막에 이 두 값의 차이와 현재 result 값의 최솟값을 갱신해준다.
여기서 하나 처리해준 것이 있는데 바로 78번 째 줄 부분이다.
만약 스타트 팀의 능력치 합과 링크 능력치 합이 같다면 그 둘의 차이는 0이다. 문제에서 배열에 들어가는 값은 1보다 크거나 같고 100보다 작거나 같은 값이므로 그 차이에 대한 절대 값은 항상 양수이다.
따라서 0이 나온다는 것은 곧 그 0이 최소값임을 의미한다.
이때는 바로 버퍼에 0을 write하고 출력 후 프로그램을 종료해주었다.
차이 값이 0이 아니라면 계속 최솟값을 갱신하다가 result 값을 출력해주면 곧 최솟값이 되고 정답이 된다!!!
3. 소스 코드
(1) 최적화 전 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int[][] map;
static int result = Integer.MAX_VALUE;
static boolean[] visited; // 팀을 나누기 위한 boolean 배열
static int N;
static BufferedWriter bw;
static BufferedReader br;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine()); // map의 크기
map = new int[N][N];
visited = new boolean[N]; // true : 스타트팀, false : 링크팀
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
setTeam(0);
bw.write(Integer.toString(result));
bw.flush();
bw.close();
br.close();
}
// 팀원을 셋팅하는 함수
// idx : 스타트 팀원을 고를 인덱스
private static void setTeam(int idx) throws Exception {
for (int i = idx; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
}
statsHap(); // 팀원이 1명이어도 된다고 했으므로
setTeam(i + 1);
visited[i] = false;
}
}
// 능력치 합을 최소가 되는 것을 찾는 함수
private static void statsHap() throws Exception {
int startTeamHap = 0;
int linkTeamHap = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 스타트팀 합
if (visited[i] && visited[j]) {
startTeamHap += map[i][j];
}
// 링크팀 합
if (!visited[i] && !visited[j]) {
linkTeamHap += map[i][j];
}
}
}
if (startTeamHap == linkTeamHap) {
bw.write("0");
bw.flush();
bw.close();
br.close();
System.exit(0);
} else {
result = Math.min(result, Math.abs(startTeamHap - linkTeamHap));
}
}
}
(2) 최적화 후 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int[][] map;
static int result = Integer.MAX_VALUE;
static boolean[] visited; // 팀을 나누기 위한 boolean 배열
static int N;
static BufferedWriter bw;
static BufferedReader br;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine()); // map의 크기
map = new int[N][N];
visited = new boolean[N]; // true : 스타트팀, false : 링크팀
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
setTeam(0, 1);
bw.write(Integer.toString(result));
bw.flush();
bw.close();
br.close();
}
// 팀원을 셋팅하는 함수
// idx : 스타트 팀원을 고를 인덱스
// depth : 스타트팀의 인원의 수
private static void setTeam(int idx, int depth) throws Exception {
for (int i = idx; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
}
if (depth <= N / 2) {
statsHap();
} else {
return;
}
setTeam(i + 1, depth + 1);
visited[i] = false;
}
}
// 능력치 합을 최소가 되는 것을 찾는 함수
private static void statsHap() throws Exception {
int startTeamHap = 0;
int linkTeamHap = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 스타트팀 합
if (visited[i] && visited[j]) {
startTeamHap += map[i][j];
}
// 링크팀 합
if (!visited[i] && !visited[j]) {
linkTeamHap += map[i][j];
}
}
}
if (startTeamHap == linkTeamHap) {
bw.write("0");
bw.flush();
bw.close();
br.close();
System.exit(0);
} else {
result = Math.min(result, Math.abs(startTeamHap - linkTeamHap));
}
}
}
4. 배운점
알고리즘 스터디를 하면서 정말 많은 것을 배우고 있다. 알고리즘을 작성하는 방법도 물론 배우지만, 모르는 것이 있을 때 넘어가지 않고 끝까지 해결한다는 마인드가 머리를 크게 때렸던 것 같다. 항상 말로만 "당연히 그래야지" 했지만, 돌이켜보면 자기합리화 하면서 "아 알지 알지" 하고 넘어갔던 것이 상당히 많았다. 혹시 이 글을 보고 있는 분 중 이런 마인드를 가지고 있었던 분이 있다면 한번 쯤 되돌아 보는 시간을 가지시는 것을 추천한다.
<문제를 풀면서 배운점>
1. visited 배열을 이용하여 백트래킹 구현 방법(이 문제와 비슷하게 접근해야 한다면 백트래킹을 의심해보자)
2. 분류를 나눌 때, 분류가 두 분류라면 boolean 배열을 사용하자
3. 문제를 풀어도 재귀에 대한 최적화에 대해 계속 고민하자!!