정올 1681 <해밀턴 순환회로>

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

JUNGOL

정 올의 해밀턴 순환 회로이다.

 

이문제는 기본적으로 백트래킹 문제이기 때문에 최대 12개의 배달 지를 순열로 놓으면서 거리를 계산하는 문제이다.

 

그러나 나는 새롭게 접근하기 위해 다익스트라 알고리즘을 응용하면서 비트 연산자를 더해 BFS로 문제를 접근해보았다.

 

dis 클래스는 next는 다음 좌표이고 d는 다음 좌표까지의 총 이동거리를 나타내고 f는 비트 연산자로 visit을 나타낸다고 보면 된다.

이렇게 총 3가지로 구성된다고 보면 된다.

 

1. 모든 곳을 다 탐색하고 다시 1로 돌아온 경우이고 최소의 거리를 출력하기 때문에 답을 입력하고 return을 수행하면 된다.
2. 자기의 회사로 돌아오는 것을 제외한 다른 배 단지로 향하는 방법이다. p.f & (1<<i)는 AND 연산자로 0이 되면 방문하지 않았다는 것을 나타낸다. p.f | (1<<i)는 방문하지 않았을 경우 방문하도록 해서 Queue에 넣어준다.
3. 자기 자신의 회사를 제외한 모든 배달 지를 다 돌았을 경우이다.

이 문제를 풀면서 주의해야 할 점은 해당 점에서 다음 배달지로 가는 길이 없을 수 도 있다는 것이다!

 

이러한 흐름으로 구성하면 쉽게 완성할 수 있을 것이다!

물론 순열로 구하면서 하는 게 더 쉽기도 하지만 새로운 방법으로 접근을 해보고 싶어 이 방법을 시도해 보았다.

 

전체 코드

package z;

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

public class so {

	public static class dis implements Comparable<dis>{
		int next;
		int d;
		int f;
		public dis(int next, int d,int f) {
			this.next = next;
			this.d = d;
			this.f=f;
		}
		@Override
		public int compareTo(dis o) {
			// TODO Auto-generated method stub
			return this.d-o.d;

		}
		
	}
	
	static int visit[],map[][],n,min=Integer.MAX_VALUE;
	static PriorityQueue<dis> q=new PriorityQueue<dis>();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(kb.readLine());
		map=new int[n][n];
		for(int i=0;i<n;i++) {
			StringTokenizer st=new StringTokenizer(kb.readLine());
			for(int j=0;j<n;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		q.add(new dis(0,0,0));
		bfs();
		System.out.println(min);
	}
	private static void bfs() {
		// TODO Auto-generated method stub
		while(!q.isEmpty()) {
			dis p=q.remove();
			if(p.f==((1<<n)-1)) {
				min=Math.min(min,p.d);
				return;
			}
			for(int i=1;i<n;i++) {
				if((p.f&(1<<i))!=0||map[p.next][i]==0)
					continue;
				else
					q.add(new dis(i,p.d+map[p.next][i],p.f|(1<<i)));
			}
			if(p.f==((1<<n)-2)&&map[p.next][0]!=0) {
				q.add(new dis(0,p.d+map[p.next][0],p.f|(1<<0)));
			}
		}
	}


}