BOJ2644 촌수계산

<Solution>

1. 사람 수 만큼의 N by N map에 촌수가 연결된 번호들을 1로 표시

2. 계산해야 되는 촌수의 노드 중 앞번호 먼저 탐색 시작

3. 연결된 다른 노드가 있는지 보고 해당 노드를 다시 탐색 반복

4. 노드를 타고 들어갈 때 마다 cnt++

5. for i가 계산해야 되는 촌수의 뒤번호랑 일치되면 flag 표시 해줘서 나머지 탐색에서 다 return

6. 백트레킹 해서 찾아야되는 경우 고려(cnt, visit_node 복구)

---

<Source Code>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2644_촌수계산 {
	
	static int[][] map;
	static int[] visit_node;
	static int cnt;
	static int map_size;
	static int target_numder;
	static int flag = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), "");
		int N = Integer.parseInt(st.nextToken());
		map_size = N;
		map = new int[N + 1][N + 1];
		visit_node = new int[N + 1];
		st = new StringTokenizer(br.readLine(), " ");
		int f = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		target_numder = s;
		st = new StringTokenizer(br.readLine(), "");
		int M = Integer.parseInt(st.nextToken());
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = 1;
			map[y][x] = 1;
		}
		
		dfs(f);
		if(flag == 1)
			System.out.print(cnt);
		else
			System.out.print(-1);
	}
	
	public static void dfs(int f) {
		visit_node[f] = 1;
		for(int i = 1; i <= map_size; i++) {
			if(flag == 1) // 이미 촌수 계산이 완료된 상태
				return;
			if(visit_node[i] == 1 || map[f][i] == 0)
				continue;
			cnt++;
			if(i == target_numder) { // 촌수 계산해야 되는 노드를 찾았다는건 더 볼필요 없으니깐 flag 변경
				flag = 1;
				return;
			}
			dfs(i);
			if(flag == 1) // 백트레킹으로 왔을 때 촌수 계산이 완료된 상태면 더 볼필요 x
				return;
			// 백트레킹으로 왔을 때 원래 값으로 만들기
			cnt--;
			visit_node[i] = 0;
		}
	}
}

좀 드럽긴 한데 일단... 백트레킹 되는 경우에도 flag == 1 경우를 고려해야되는 걸 빼먹어서 좀 걸림... dfs 디버깅 너무 어려워...