10552 : DOM - JAVA

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

 

기본적인 너비우선탐색, 깊이우선탐색이다.

https://www.acmicpc.net/problem/1260 1260번과 상당히 유사하지만 답 도출방식만 살짝 바뀐 정도이다.

 

너비우선 탐색으로 푸는 방법은 Queue에 기본적으로 하나 집어넣고, 반복문 안에 들어가서 큐에 들어있는 값을 뺀다음 다음 연결된 부분을 찾아서 큐에 집어넣고 방문처리를 한뒤 빼기를 반복하는 풀이로 해결할수 있고

 

깊이우선 탐색은 재귀 및 스택으로 연결된 부분을 방문하여 최종 방문까지 카운트 처리후 그 숫자를 출력하는 방식이다.

 

소스코드

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

public class sol116 {
	static int cnt = 0;
	static int[] connect;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());
		connect = new int[m+1];
		check = new boolean[m+1];
 		while(n-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(connect[b]==0) {
				connect[b] = a;
			}
		}
 		dfs(p);
 		bw.write(String.valueOf(cnt));
 		bw.flush();
 		bw.close();
 		br.close();
	}
	public static void dfs(int v) {
		if(check[v]) {
			cnt=-1;
		}
		else if(connect[v] != 0) {
			check[v] = true;
			cnt++;
			dfs(connect[v]);
		}
	}
}