백준 1563 - 외판원 순회2

Java

1563 번 - 외판원 순회2

문제

접근 방법

DFS로 풀되, 비트연산을 통해 방문 여부를 체크하였다. int형인 vis로 체크하였으며, 2진수로 변환하였을 때 각 자리수가 노드를 뜻한다.
즉, 0 이면 아무것도 방문하지 않은 것이며
1이면 1번째 node 방문, (1)
2이면 2번째 node 방문, (10)
3이면 1, 2번째 node 방문, (11)
5이면 2, 3번째 node 방문 (110)
을 뜻한다.

방문 여부 체크는 비트 연산을 사용하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	map = new int[n][n];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	result = Integer.MAX_VALUE;
    	DFS(0,0,0,0,1);

    	System.out.println(result);
    	br.close();
	}

	static void DFS(int st, int curN, int sum, int cnt, int vis) {
		if(sum > result)
			return;
		if(cnt == n - 1 && map[curN][st] != 0) {
			result = Math.min(result, sum + map[curN][st]);
			return;
		}

		for(int nextN = 0; nextN < n; nextN++) {
			// 길이 이어져있는지 확인
			if(nextN == curN || map[curN][nextN] == 0)
				continue;
			// 방문 여부 체크
			if((vis & 1 << nextN) != 0) {
				continue;
			}

			DFS(st, nextN, sum + map[curN][nextN], cnt + 1, vis | 1 << nextN);
		}

	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점