[Java/백준/BFS, DFS] 2644번: 촌수계산

문제

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

BFS 코드

adjacent라는 ArrayList<Integer>[] 배열을 만들어서 각 사람들의 부모-자식 관계 사람들을 추가해준다.

 

BFS

queue 안에 알아야 할 사람 중 한명(start)를 넣고 거기서부터 BFS로 검사해 나간다.

visited[사람]에는 start로부터 몇칸씩 떨어져 있는지가 입력된다.

queue에서 제일 처음 것을 빼냈을 때 이것이 start와 관계를 묻는 사람(end)이면 return된다.

 

main

visited 배열의 end 자리가 0인 경우는 start에 도달하지 못했다는 의미이므로 -1를 출력한다.

이 경우가 아니라면 visited[end]의 값을 그대로 출력한다.

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

public class Main {
    static ArrayList<Integer>[] adjacent;
    static int[] visited;
    public static void bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while(!queue.isEmpty()) {
            int r = queue.poll();
            
            //r이 찾던 사람이면
            if(r==end) {
            	return;
            }
            
            for(int n : adjacent[r]) {
            	if(visited[n]==0) {
                    visited[n]= visited[r]+1;
                    queue.offer(n);
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
        /*
        num : 사람 수
        p1 : start, p2 : end
        */
        int num = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split("\\s");
        int p1 = Integer.parseInt(strArr[0]);
        int p2 = Integer.parseInt(strArr[1]);
		
        //adjacent 초기화
        adjacent = new ArrayList[num+1];
        for(int i=0; i<=num; i++)
            adjacent[i] = new ArrayList<Integer>();
			
        visited = new int[num+1];
		
        int adj_num = Integer.parseInt(br.readLine());
        for(int i=0; i<adj_num; i++) {
            String[] strArr2 = br.readLine().split("\\s");
            int a = Integer.parseInt(strArr2[0]);
            int b = Integer.parseInt(strArr2[1]);
            adjacent[a].add(b);
            adjacent[b].add(a);
        }
        bfs(p1,p2);
		
        String answer = visited[p2]>0 ? Integer.toString(visited[p2]) : "-1";
        bw.write(answer+"\n");
        bw.flush();	
    }
}

 

DFS 코드

Queue를 Stack으로만 바꿔주면 해결된다.

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

public class Main {
	static ArrayList<Integer>[] adjacent;
	static int[] visited;
	public static void dfs(int start, int end) {
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		while(!stack.isEmpty()) {
			int r = stack.pop();
			if(r==end) {
				return;
			}
			for(int n : adjacent[r]) {
				if(visited[n]==0) {
					visited[n]= visited[r]+1;
					stack.push(n);
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		String[] strArr = br.readLine().split("\\s");
		int p1 = Integer.parseInt(strArr[0]);
		int p2 = Integer.parseInt(strArr[1]);
		
		adjacent = new ArrayList[num+1];
		for(int i=0; i<=num; i++)
			adjacent[i] = new ArrayList<Integer>();
			
		visited = new int[num+1];
		
		int adj_num = Integer.parseInt(br.readLine());
		for(int i=0; i<adj_num; i++) {
			String[] strArr2 = br.readLine().split("\\s");
			int a = Integer.parseInt(strArr2[0]);
			int b = Integer.parseInt(strArr2[1]);
			adjacent[a].add(b);
			adjacent[b].add(a);
		}
		dfs(p1,p2);
		
		String answer = visited[p2]>0 ? Integer.toString(visited[p2]) : "-1";
		bw.write(answer+"\n");
		bw.flush();
		
	}
}