[백준] 촌수계산 2644 - JAVA

문제

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

2644번: 촌수계산

 

코드

BFS

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

public class Main {

	static ArrayList<Integer> arr[];
	static int visit[];
	static int a, b;
	static int result = -1;
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList [n+1];
		visit = new int[n+1];
		for(int i=0;i<=n;i++) {
			arr[i] = new ArrayList<>();
		}
		
		st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		
		int m = Integer.parseInt(br.readLine());
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x].add(y);
			arr[y].add(x);
		}
		
		Arrays.fill(visit, -1);
		bfs();
		System.out.print(result);
		
		
	}
	
	static void bfs() {
		Queue<Integer> que = new LinkedList<>();
		
		que.add(a);
		visit[a] = 0;
		
		while(!que.isEmpty()) {
			int cur = que.poll();

			if(cur == b) {
				result = visit[cur];
				return;
			}
			for(int next : arr[cur]) {
				if(visit[next] != -1) continue;
				que.add(next);
				visit[next] = visit[cur]+1;
			}
		}
		
	}
		
}

DFS

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

public class Main {

	static ArrayList<Integer> arr[];
	static boolean check[];
	static int a, b;
	static int result = -1;
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList [n+1];
		check = new boolean[n+1];
		for(int i=0;i<=n;i++) {
			arr[i] = new ArrayList<>();
		}
		
		st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		
		int m = Integer.parseInt(br.readLine());
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			arr[x].add(y);
			arr[y].add(x);
		}
		
		dfs(a, 0);
		System.out.print(result);
		
		
	}
	
	static void dfs(int start, int count) {
		if(start == b) {
			result = count;
			return;
		}
		
		check[start] = true;
		for(int next : arr[start]) {
			if(check[next]) continue;		
			dfs(next, count+1);
		}
	}
	
}