[정올] JAVA - 1681.해밀턴 순환회로

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030

JUNGOL

생각

모든 노드들을 방문한뒤 다시 처음 시작점으로 돌아와야 할때 최소비용을 구하는 문제이다. 문제를 다 풀고나니 외판원 순회문제군요ㅎ.ㅎ

 

먼저 인접리스트를 사용하여 그래프의 정보를 나타냈습니다. 이때 비용이 0인 경우는 갈 수 없는 경우이므로 인접리스트에 담아주지 않습니다. 갈 수 있는 경우만 인접리스트에 추가해줍니다.

 

dfs를 사용하여 현재 노드에서 내가 다음 노드로 갈수있는지 방문여부를 체크한 다음에 재귀호출하여 갈 수 있는 경우를 모두 탐색한다음 다시 돌아와 visited를 해제시켜줍니다.

 

모든 정점에 대한 방문여부를 반복문을 돌려 탐색할수도있지만 파라미터로 준 depth에서 카운트를 해주기 때문에 depth 체크를 통해 모든 정점에 대한 방문여부를 체크했습니다. -> 파이썬에서는 all() 함수를 써서 체크하면 될듯합니다.

 

이 문제에서 제가 정의한 dfs 함수의 역할은 현재까지 거쳐온 노드의 비용을 계산하여 가지고 있다가 모든 노드들을 방문하고 다시 처음 시작 정점으로 도착하였을때 최소 비용이면 업데이트 시켜주는 역할입니다. 이때 비용이 현재 내가 계산한 정답보다 크다면 바로 return 시켜버리는 가지치기 조건을 추가해줘야합니다!!

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class JUNGOL_1681_해밀턴순환회로 {
	
	static class Node {
		int node, weight;
		
		public Node(int node, int weight) {
			super();
			this.node = node;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Node [node=" + node + ", weight=" + weight + "]";
		}
		
	}
	static int N;
	static ArrayList<Node>[] adjList;
	static boolean[] visited;
	static int ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		
		adjList = new ArrayList[N];
		visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			adjList[i] = new ArrayList<Node>();
		}
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				int cost = Integer.parseInt(st.nextToken());
				if(cost == 0) continue;
				adjList[i].add(new Node(j,cost));
			}
		}
		//System.out.println(Arrays.deepToString(adjList));
		ans = Integer.MAX_VALUE;
		solve(0,0,0);
		System.out.println(ans);
		
		
	}
	private static void solve(int now, int depth, int cost) {
		if(cost >= ans) return; // 이 리턴조건 추가해야 시간초과 해결!!!
		
		if(now == 0 && depth == N) {	
			ans = Math.min(ans, cost);
			return;
		}
		
		for (int i = 0; i < adjList[now].size(); i++) {
			Node next = adjList[now].get(i);
			if(!visited[next.node]) {
				visited[next.node] = true;
				solve(next.node, depth+1, cost + next.weight);
				visited[next.node] = false;
			}
			
		}
		
	}

}