문제 url:
스타트와 링크
문제:
🤔 문제 알아보기
필자는 초짜라서 이번 문제가 쉽지 않았다.(이전 문제는 좀 쉽게 느껴졌는데)
그럼에도 문제를 이해하고 접근한 과정에 대해서는 다른 이들과 유사하다고 생각해 필지가 이해한 바와 다른 이들이 푼 방식을 섞어 설명을 해보도록 하겠다.
먼저, 스타트팀과 링크팀 총 두 팀으로 이루어진다. 또한 각 팀은 짝수명만큼 인원이 들어간다.
그 후, 팀원은 번호를 가지고 있는데, 팀원과의 번호를 조합하여 능력치를 얻을 수 있다.
즉, 스타트 팀에 1번과 3번이 존재한다면!
S라는 2차원 배열에 들어가 있는 능력치 표에서 좌표값으로 능력치를 계산할 수 있다는 얘기이다.
즉, 1번과 3번은 [1][3] 과 [3][1]의 좌표값으로 계산할 수 있고, 능력치 배열 S에서 이를 계산하면 [1][3] = 2 / [3][1] = 0으로 계산할 수 있다.
그럼, 각 팀에 3명씩 들어가면 어떨까? 각 팀에 1, 2, 3번이 들어갔다고 가정하면
[1][2] , [2][1] / [1][3] , [3][1] / [2][3], [3][2] 이렇게 능력치를 계산할 수 있다.
자! 그럼 능력치를 계산하는 방법을 알아봤고, 이제 문제를 알아보자면
스타트팀과 링크팀에서 위에서 구한 능력치를 빼는데, 해당 값이 최소가 되는 능력치의 차를 구해야 한다.
이를 구하는 방법을 코드와 함께 알아보자
🐱👤 실제 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[][] S;
static int N;
static boolean[] visited;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
S = new int[N][N];
visited = new boolean[N];
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
S[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0);
System.out.println(min);
}
static void dfs(int depth, int at) {
if(depth == N/2) {
/*
* 능력치의 차를 구한 후 최솟값을 호출하는 메서드 호출
*/
diff();
return;
}
for(int i = at; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
dfs(depth + 1, i + 1);
visited[i] = false;
}
}
}
/*
* 각 팀별 능력치를 구한 다음 그 중
*/
static void diff() {
int start_sp = 0;
int link_sp = 0;
for(int i = 0; i < N-1; i++) {
for(int j = i + 1; j < N; j++) {
/*
* visited가 true인 경우는 start팀이 꾸려진 번호를 의미
*/
if(visited[i] && visited[j]) {
start_sp += S[i][j] + S[j][i];
}
/*
* visitied가 false인 경우는 link팀이 꾸려진 번호를 의미
*/
else if(!visited[i] && !visited[j]) {
link_sp += S[i][j] + S[j][i];
}
}
}
int res = Math.abs(start_sp - link_sp);
/*
* 0인 경우는 모든 경우에서 나올 수 있는 가장 낮은 값이기 때문에
* 출력과 그대로 시스템 종료
* 이를 통해 불필요한 반복을 줄일 수 있다.
*/
if(res == 0) {
System.out.println(res);
System.exit(0);
}
min = Math.min(min, res);
}
}
😎 코드 풀이 및 해석
1번 코드
static void dfs(int depth, int at) {
if(depth == N/2) {
/*
* 능력치의 차를 구한 후 최솟값을 호출하는 메서드 호출
*/
diff();
return;
}
for(int i = at; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
dfs(depth + 1, i + 1);
visited[i] = false;
}
}
}
해당 코드는 스타트팀과 링크팀을 구하는 메서드이다.
먼저, depth는 깊이를 나타내는 변수인데 간단하게 얘기하자면 각 팀의 인원수라고 생각하면 이해하기 쉬울 것이다.
즉, 현재 4명이 존재한다고 가정하면 각 팀은 각각 2명씩 인원을 배정받는다.
그럼 depth가 2가 된다는건 2명씩 인원이 들어왔다고 보면 된다.
그런 다음 인원을 배정해주는 반복문이다.
먼저, visited배열을 통해 방문한 적이 있는지 없는지 여부를 파악해 인원수를 채워줄 것이다.
그래서 만약 인원이 존재하지 않으면 동작하는데, visited[i] = true를 주어 재귀 호출시 해당 숫자에 접근하지 못하도록 한 후 재귀호출을 진행한다.
여기서 중요한 것이 있다.
필자는 해당 부분에서 시간 초과가 떠서 꽤 시간이 걸렸었다.
아무리 봐도 코드가 다 똑같은데 왜 난 안되지.. 찾다가 여기서 문제임을 알 수 있었다.트러블 슈팅
// 초기 코드 for(int i = at; i < N; i++) { if(!visited[i]) { visited[i] = true; dfs(depth + 1, ★at + 1); visited[i] = false; } } // 변경 코드 for(int i = at; i < N; i++) { if(!visited[i]) { visited[i] = true; dfs(depth + 1, ★i + 1); visited[i] = false; } }dfs를 호출하는 과정에서 at 파라미터 값이 다른걸 확인할 수 있다.
두괄식으로 먼저 결과먼저 설명하자면,
초기 코드는 dfs 방식으로 모든 경우의 수를 고려하는 과정을 거친다.만약 스타트팀에
1,2,3가 들어온다고 가정하자 그러면
여기서3,2,1이나 1,3,2은1,3,2와 똑같은 결과를 가져온다.
그러면3,2,1과 1,2,3을 굳이 구해줄 필요가 있을까?
위의 초기코드는 필자가 설명하는 것과 같이 동작하게 된다.하지만! 변경 코드는 조합론에 맞추어 중복되는 코드는 하나만 구하도록 한 것이다.
현재 인덱스 기준으로 1씩 더한 값을 넘겨 주기 때문에 현재 인덱스 이하 또는 현재 인덱스각 들어갈 수 없는 구조이기 때문에
위의3,2,1과 1,3,2구조가 나올 수 없는 것이다.굉장히 큰 차이를 가져오기 때문에 반드시 알아놓는게 좋은 것 같다!
오히려 이렇게 틀림으로써 이런 중요성을 알 수 있었던 것 같다.
자, 다시 코드로 돌아와서
그럼 visited가 현재 true라면? 스타트팀을 구한 것이고
자동적으로 false인 팀은 링크팀이 되는 구조이다.
2번 코드
static void diff() {
int start_sp = 0;
int link_sp = 0;
for(int i = 0; i < N-1; i++) {
for(int j = i + 1; j < N; j++) {
/*
* visited가 true인 경우는 start팀이 꾸려진 번호를 의미
*/
if(visited[i] && visited[j]) {
start_sp += S[i][j] + S[j][i];
}
/*
* visitied가 false인 경우는 link팀이 꾸려진 번호를 의미
*/
else if(!visited[i] && !visited[j]) {
link_sp += S[i][j] + S[j][i];
}
}
}
/*
* 만약 링크팀의 능력치가 더 크면 음수가 나올 수 있기 때문에
* 음수를 방지하고자 절댓값을 받도록 한다
*/
int res = Math.abs(start_sp - link_sp);
/*
* 0인 경우는 모든 경우에서 나올 수 있는 가장 낮은 값이기 때문에
* 출력과 그대로 시스템 종료
* 이를 통해 불필요한 반복을 줄일 수 있다.
*/
if(res == 0) {
System.out.println(res);
System.exit(0);
}
min = Math.min(min, res);
}능력치를 구하는 코드로, 이는 특별히 어려운 것이 없다.
2차원 배열이기 때문에 2중 for문을 사용한 것이며
위에서 설명했듯 visited가 true는 스타트팀. false는 링크팀이다.
그리고 능력치는 S[i][j]의 값과 S[j][i]값의 합 으로 이루어 진다고 했으니.
위와 같이 구할 수 있다.
🤢 회고
필자에게 아직까지 백트래킹과 조합이 쉽지 않은 것 같다. 그래도 이전보다는 문제를 해석하는 능력이 조금씩 발전하고 있음을 느껴 나름의 보람을 느끼고는 있지만, 구현하는 능력이 부족하다는게 느껴져 아직까지는 부족하다고 생각한다.
필자도 하루 빨리 타 코드를 보지않고 쉬리릭 푸는 수준까지 도달하고 싶다.
💜 참고 자료
