[JAVA]백준_14889_스타트와 링크

문제링크

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

14889번: 스타트와 링크

 

 

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

public class Main {
	static int N;
	static int map[][];
	static boolean isVisited[];
	static int result = Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		isVisited = 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/2명?
		dfs(0,0);
		System.out.println(result);
	}
	
	static void dfs(int idx,int cnt) {
		if(result == 0) return;
		if(cnt == (N/2)) { //계산
			calc();
			return;
		}
		
		for(int i=idx;i<N;i++) {
			if(!isVisited[i]) {
				isVisited[i] = true;
				dfs(i,cnt+1);
				isVisited[i] = false;
			}
			
		}
		
		
	}
	
	static void calc() {
		int start[] = new int[N/2];
		int link [] = new int[N/2];
		int start_idx=0;
		int link_idx=0;
		int start_sum=0;
		int link_sum = 0;
		
		for(int i=0;i<N;i++) {
			if(isVisited[i]) start[start_idx++] = i;
			else link[link_idx++] =i;
		}
		
		for(int i=0;i<N/2;i++) {
			for(int j=i+1;j<N/2;j++) {
				if(i == j) continue;
				
				int start_x = start[i];
				int start_y = start[j];
				
				start_sum +=( map[start_x][start_y] + map[start_y][start_x]);
				
				start_x = link[i];
				start_y = link[j];
				
				link_sum +=(map[start_x][start_y]+map[start_y][start_x]);
			}
		}
		
		result = Math.min(result, Math.abs(start_sum-link_sum));
	}
}

 

 

시간 초과 나서 고생했다.

 

일단 DFS로 풀었다.

isVisited이용해서 방문하고 안하고를 체크해주어 N/2가 되면 계산을 해주었다.

 

시간초과가 발생한 이유는 dfs를 돌릴 떄 for문을 idx로 시작안하고 0으로 시작했더니 시간초과가 발생하더라.

그리고 혹시 몰라서 result = 0이 되면 이게 제일 최소값이니까 그 이후에는 계산 안하고 return 하도록 만들어주었다.