[백준 2644] 촌수계산(Java)

1. 문제

www.acmicpc.net/problem/2644

2644번: 촌수계산

2. 풀이

• DFS를 사용하여 풀었다.
• s를 출발점으로 잡았고, 도착점e까지 갈때  촌수(depth)를 증가시켰다.
• 촌수가 0일때, -1을 출력하였다.

3. 코드

package exam;

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

public class 촌수계산 {

	static int N,s, e, M;
	static int[][] map;
	static boolean[] visited;
	static int cnt;
	
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//br = new BufferedReader(new StringReader(src));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		s = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(br.readLine());
		
		map = new int[N+1][N+1];
		visited = new boolean[N+1];
		
		for(int i =0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map[a][b]=map[b][a]=1;
		}
		
		dfs(s,0);
		if(cnt>0) {
			System.out.println(cnt);
		}else System.out.println(-1);
		
	}
	static void dfs(int start, int depth) {
		if(start==e) {
			cnt = depth;
			return;
		}
		visited[start]=true;
		for(int i = 1; i<=N;i++) {
			if(map[start][i]==1 && !visited[i]) {
				visited[i]=true;
				dfs(i, depth+1);
				visited[i] = false;
			}
		}
		
	}
	
	
	static String src = 
			"9\r\n" + 
			"7 3\r\n" + 
			"7\r\n" + 
			"1 2\r\n" + 
			"1 3\r\n" + 
			"2 7\r\n" + 
			"2 8\r\n" + 
			"2 9\r\n" + 
			"4 5\r\n" + 
			"4 6";
}

반응형