[백준] 15661 링크와 스타트 - 완전탐색 (DFS) JAVA

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

15661번: 링크와 스타트

코드설명

완전탐색을 활용하여 일종의 조합을 구한뒤 최대값과 최소값의 차이를 구하는 문제입니다.

 

문제 조건에

- 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.

위의 조건이 이 문제의 핵심이라고 생각합니다.그렇게 처리하기 위해 combinationNumber라는 전역 변수를 선언하여, 

// N개일떄, (1 개, N-1 개 ), (2개, N-2개), (3개, N-3개) ...
for(int i=1; i<N;i++) { 
    combinationNumber = i;
    simulate(0, 0);
}

 

simulate함수의 일부 중

level == combinationNumber 일떄의 조건을 걸어서 처리합니다.

if(level == combinationNumber) {
    int startTeam = 0; 		// visited[i] 가 FALSE 일경우 START 팀
    int linkTeam = 0;		//	visited[i] 가 TRUE 일경우 LINK 팀

    //i와 j가 같으면 어처피 0 이기에 j = i+1 부터 시작하도록 처리
    for(int i=0;i<N-1;i++) { 
        for(int j=i+1;j<N;j++) { 
            if(visited[i] == true && visited[j] == true) { //startTeam
                startTeam += map[i][j] + map[j][i]; //한번에 다 대칭모양을 다 더해줍니다.
            }
            else if(visited[i] == false && visited[j] == false) { //linkTeam
                linkTeam += map[i][j] +map[j][i]; //한번에 다 대칭모양을 다 더해줍니다.
            }
        }
    }

    result = Math.min(result,  Math.abs(startTeam - linkTeam));
    return ;
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;



public class Main {
	
	public static int N;
	public static int[][] map;
	public static int combinationNumber=0;
	public static boolean[] visited;
	public static int result = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());

    	map = new int[N][N];
    	visited = new boolean[N];
    	
    	for(int i=0; i< N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	// N개일떄, (1 개, N-1 개 ), (2개, N-2개), (3개, N-3개) ...
    	for(int i=1; i<N;i++) { 
    		combinationNumber = i;
    		simulate(0, 0);
    	}
    	System.out.println(result);
    }
    
    public static void simulate(int idx, int level) {
    	if(level == combinationNumber) {
    		int startTeam = 0; 		// visited[i] 가 FALSE 일경우 START 팀
    		int linkTeam = 0;		//	visited[i] 가 TRUE 일경우 LINK 팀
    		
    		//i와 j가 같으면 어처피 0 이기에 j = i+1 부터 시작하도록 처리
    		for(int i=0;i<N-1;i++) { 
    			for(int j=i+1;j<N;j++) { 
    				if(visited[i] == true && visited[j] == true) { //startTeam
    					startTeam += map[i][j] + map[j][i]; //한번에 다 대칭모양을 다 더해줍니다.
    				}
    				else if(visited[i] == false && visited[j] == false) { //linkTeam
    					linkTeam += map[i][j] +map[j][i]; //한번에 다 대칭모양을 다 더해줍니다.
    				}
    			}
    		}
    		
    		result = Math.min(result,  Math.abs(startTeam - linkTeam));
    		return ;
    	}
    	
    	for(int i=idx;i<N;i++) {
    		if(visited[i] == true) continue;
    		visited[i] = true;
    		simulate(i + 1, level + 1);
    		visited[i] = false;
    	}	
    }
}