[백준] 2644 촌수계산 - DFS(깊이우선탐색) + 비트마스킹(BitMask) JAVA

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

코드설명

DFS(깊이우선탐색) + 비트마스킹(BitMask) 을 활용합니다.

 

가장 가까운 촌수를 찾아서 값을 가져오면 됩니다. DFS와 BFS로 하는것이 가장 간단해보여서 DFS로 구현했습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K, M;
	public static int answer = 0;
	public static int[][] matrix;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken()) - 1;
		int B = Integer.parseInt(st.nextToken()) - 1;
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		matrix = new int[N][N];
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			matrix[x][y] = 1;
			matrix[y][x] = 1;
		}
		
		System.out.println(DFS(0, A, B, (1 << A)));
		
	}
	
	public static int DFS(int depth, int now, int target, int visited) {
		if(now == target) {
			return depth;
		}
		int ret = -1;
		for(int next=0; next<N; next++) {
			if(matrix[now][next] == 1 && (visited & (1 << next)) == 0 ) {
				ret = Math.max(ret, DFS(depth + 1, next, target, visited + (1 << next)));
			}
		}
		return ret;
	}

}