[알고리즘] 백준 10971 외판원순회 - 자바

 

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

10971번: 외판원 순회 2

 

 

[풀이 코드]

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

public class BOJ_10971_외판원순회2 {
	static int N;
	static int[][] array;
	static boolean[] visited;
	static long min = Integer.MAX_VALUE; // 각 행렬의 성분은 1,000,000이하의 양의 정수
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		array = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<N; i++) {
			visited = new boolean[N];
			visited[i] = true;
			dfs(i, i, 0);
		}
		
		System.out.println(min);
		
	}
	static void dfs(int start, int end, int sum) {
		if(visitCheck()) { 
			if(array[start][end] != 0) {
				sum += array[start][end];
				min = Math.min(min, sum);
			}
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(array[start][i] != 0 && !visited[i]) {
				visited[i] = true;
				dfs(i, end, sum + array[start][i]);
				visited[i] = false;
			}
		}
	}
	
	static boolean visitCheck() { // visited 탐색
		for(int i=0; i<N; i++) {
			if(!visited[i])
				return false;
		}
		return true;
	}

}

 

• 설계? 구상을 꼼꼼히 해서 코딩하는데 시간이 오래 걸리진 않았다.. 어느 정도 필기를 하고 푸는 건 좋지만 좀 간략히  쓰는 연습을 해야겠다.
• 각 행렬의 성분은 1,000,000 이하의 양의 정수 라는 문장을 보고 min값을 1000000을 줬는데 이 부분이 문제였던 것 같다. 뭐가 문제인지 몰라서 계속 헤매다가 블로그를 참고했다... 다 풀었는데ㅜ

쉬운 게 없다~

 

[코드 수정]

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

public class BOJ_10971_외판원순회2_다른풀이 {
	private static int N; // 도시의 수
	private static int[][] map; // 경로
	private static boolean[] isVisited; // 도시 방문 여부
	private static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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());
			}
		}
		for (int i = 0; i < N; i++) {
			isVisited[i] = true;
			dfs(0, i, i, 0);
		}
		System.out.println(answer);
	}

	private static void dfs(int depth, int start, int prev, int cost) { // 깊이, 첫시작도시, 이전탐색도시, 총비용,																						// 도시 방문여부
		if (depth == N - 1) {
			if (map[prev][start] != 0) {
				answer = Math.min(answer, cost + map[prev][start]); // 다시 시작점으로 돌아오는 경우 플러스
			}
			return;
		}
		for (int i = 0; i < N; i++) {
			if (!isVisited[i] && map[prev][i] != 0) {
				isVisited[i] = true;
				dfs(depth + 1, start, i, cost + map[prev][i]);
				isVisited[i] = false;
			}
		}
	}
}

• 친구가 풀었던 풀이를 참고했다. dfs함수 재귀문안에 매개변수를 추가했을 뿐인데 이렇게 간단하다니..
• 그리고 이전 코드에서는 visited방문배열을 dfs함수안에 들어갈때마다 모든 도시가 방문처리가 되었는지 체크를 해줬는데 그럴 필요가 없었다. 어차피 depth가 N-1개가 된다면 모두 true가 되었을테니까.. 이 생각을 왜 못했지