[백준] 14889번 : 스타트와 링크 - JAVA [자바]

 

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

문제 

 

간단한 조합 문제이다. 하지만 알고리즘을 안푼지 2개월쯤 되니 조합 작성 코드를 까먹어서 자괴감이....

그래서 단순히 Git에 기록을 남기는 것이 아니라 느낀점을 블로그에 남기기로 했다.

 

조합 코드는 아래와 같다.

static void combi(int idx, int count) {
	if(count == 몇개뽑을건지 숫자 결) {
		System.out.println(Arrays.toString(visit));
		return;
	}
	 
	for(int i = idx; i < N; i++) {
		if(!visit[i]) {
			visit[i] = true;
			combi(i + 1, count + 1);
			visit[i] = false;
		}
	}
}

 

위 코드를 실행시켜보면

 

이와 같이 visit 배열에서 뽑힌 것들은 true로 나오는 것을 알 수 있다.

 

이 문제는 2개의 팀을 나누는 것을 요구한다.

즉 조합 코드를 아래와 같이 변경해주고 스타트팀과 링크팀의 차이를 계산하는 함수를 추가해주면 풀리게 된다.

 

static void combi(int idx, int count) {
	if(count == N / 2) {
    // 스타트팀과 링크팀의 차이를 계산하는 함수 추가.
		calculation();
		return;
	}
	 
	for(int i = idx; i < N; i++) {
		if(!visit[i]) {
			visit[i] = true;
			combi(i + 1, count + 1);
			visit[i] = false;
		}
	}
}

static void calculation() {
	int startTeam = 0;
	int linkTeam = 0;
		
	for(int i = 0; i < N; i++) {
		for(int j = i + 1; j < N; j++) {
		
			if(visit[i] && visit[j]) {
				startTeam += map[i][j] + map[j][i];
			}
			else if(!visit[i] && !visit[j]) {
				linkTeam += map[i][j] + map[j][i];
			}
		}
	}
		
	min = Math.min(min, Math.abs(startTeam - linkTeam));
}

 

---

전체 코드

public class Main {
    static int N;
    static boolean[] visit;
    static int[][] map;
    static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	N = Integer.parseInt(in.readLine());
    	map = new int[N][N];
    	visit = new boolean[N];
    	
    	for(int i = 0; i < N; i++) {
    		st = new StringTokenizer(in.readLine());
    		for(int j = 0; j < N; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	combi(0, 0);
    	System.out.println(min);
    }
	
	static void combi(int idx, int count) {
		// 팀 조합이 완성될 경우
		if(count == N / 2) {
			calculation();
			return;
		}
	 
		for(int i = idx; i < N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				combi(i + 1, count + 1);
				visit[i] = false;
			}
		}
	}
	
	static void calculation() {
		int startTeam = 0;
		int linkTeam = 0;
		
		for(int i = 0; i < N; i++) {
			for(int j = i + 1; j < N; j++) {
				
				if(visit[i] && visit[j]) {
					startTeam += map[i][j] + map[j][i];
				}
				else if(!visit[i] && !visit[j]) {
					linkTeam += map[i][j] + map[j][i];
				}
			}
		}
		
		min = Math.min(min, Math.abs(startTeam - linkTeam));
	}
}

---

결과