14889번 : 스타트와 링크

문제

14889번 : 스타트와 링크

 

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

 

문제 풀이

public class Main {
	public static int min = Integer.MAX_VALUE;
	public static int [][] arr;;
	public static int n;
	public static boolean [] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());
		arr = new int[n][n];
		visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(0,0);
		System.out.println(min);
		
	}
	public static void dfs(int index, int dep) {
		if (dep == n / 2) {
			int link = 0;
			int start = 0;

	        for (int i = 0; i < n; i++) {
	            for (int j = i + 1; j < n; j++) {
	                if (visited[i] && visited[j]) { // 같은 팀인 경우
	                    start += arr[i][j] + arr[j][i];
	                } else if (!visited[i] && !visited[j]) { // 다른 팀인 경우
	                    link += arr[i][j] + arr[j][i];
	                }
	            }
	        }
			min = Math.min(min, Math.abs(start-link));
			return;
		}
		for (int i = index; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(i,dep+1);
				visited[i] = false;
			}
		}
	}
}

 

• 2번의 시간 초과를 겪었다 
  • 맨처음에는 이런식으로 2중 포문을 돌렸고 for문안에 for문이 2개인 것으로 상당히 로직이 구렸다.
  • 아래에는 두번 째 for문이 

// 기존 코드
for (int i = 0; i < n; i++) {
	if (!visited[i]) {
		for (int j = 0; j < n; j++) {
			if (i != j && !visited[j]) {
				link += arr[i][j];
			}
		}
	}
	else {
		for (int j = 0; j < n; j++) {
			if (i != j && visited[j]) {
				start += arr[i][j];
			}
		}
	}
}

// 새로 짠 코드
for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
		if (visited[i] && visited[j]) { // 같은 팀인 경우
	    	start += arr[i][j] + arr[j][i];
            } else if (!visited[i] && !visited[j]) { // 다른 팀인 경우
	            link += arr[i][j] + arr[j][i];
	        }
	}
}

• 저런 식으로 훨씬 간결하게 코드를 짰음에도 시간 초과가 떠서 조합을 짜는 부분을 0부터가 아닌 index 값을 가져와서 조합을 짜는 방법으로 변경하여 시간 초과를 해결 했다.

// 원래 코드
public static void dfs(int dep) 

for (int i = 0; i < n; i++) {
	if (!visited[i]) {
		visited[i] = true;
		dfs(i, dep+1);
		visited[i] = false;
	}
}


//새로 짠 코드

public static void dfs(int index, int dep) 

for (int i = index; i < n; i++) {
	if (!visited[i]) {
		visited[i] = true;
		dfs(i, dep+1);
		visited[i] = false;
	}
}