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

설명

2차원 배열을 이용하여, 시작점(start)부터 종료지점(end)까지 촌수를 계산한다.

BFS

• 방문할 지점을 나타내는 queue의 크기가 0이 될 때까지, 출발지점부터 방문할 지점들을 queue에 넣는다.
  • queue에 들어가는 결과들은 해당 지점과 연결된 지점과 연결된 지점 중, 방문하지 않은 점을 말한다.
• queue에 들어간 지점은 방문표시한다.
• queue에서 꺼낸 값이(= 방문할 지점), 종료지점과 같다면 반복문을 종료하고 출력한다.

DFS

• 방문할 지점은 방문 표시한다.
• 방문할 지점이 종료지점과 같다면 값을 반환하고 종료한다.
• 노드의 개수만큼, 반복문을 돌면서 노드와 연결된 지점이 방문하지 않았다면 그 점부터 DFS를 순환호출한다.
  • 이때 촌수를 나타내는 count 개수를 1씩 증가한다.

코드

BFS

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2644 {
    static int n, m;
    static int start, end;
    static boolean[][] family;
    static boolean[] visitied;
    static int count;
    static Queue<Integer> queue;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P2644/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer str;

        count = 0;

        // 전체 사람의 수
        n = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        // 계산해야하는 촌수
        str = new StringTokenizer(br.readLine());
        start = Integer.parseInt(str.nextToken());
        end = Integer.parseInt(str.nextToken());

        // 부모 자식들 간의 관계 개수
        m = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        family = new boolean[n + 1][n + 1];
        visitied = new boolean[n + 1];      // 방문 여부를 채크한다.
        nums = new int[n + 1];

        // 관계 정보를 저장한다.
        for (int i = 0; i < m; i++) {
            str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());

            family[a][b] = true;
            family[b][a] = true;
        }

        BFS();

        if (nums[end] == 0) {
            sb.append(-1);
        } else {
            sb.append(nums[end]);
        }
        System.out.println(sb);
    }
    
    
    private static void BFS() {
        queue = new LinkedList<>();

        // start와 end 사이의 촌수를 찾으면서 a에서부터 출발하여 queue에 넣는다.
        queue.add(start);
        visitied[start] = true;

        while (!queue.isEmpty()) {

            // 확인할 사람을 queue에서 꺼낸다.
            int willVisit = queue.poll();
            // 비교 대상 찾으면 촌수(결과) 저장
            System.out.println("willVisit = " + willVisit);
            if (willVisit == end) {
                break;
            }
            for (int i = 1; i <= n; i++) {
                if (!visitied[i] && family[willVisit][i]) {
                    queue.add(i);
                    visitied[i] = true;
                    nums[i] = nums[willVisit] + 1;
                }
            }
        }
    }
}

DFS

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2644 {
    static int n, m;
    static int start, end;
    static boolean[][] family;
    static boolean[] visitied;
    static int count;
    static Queue<Integer> queue;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer str;

        count = 0;

        // 전체 사람의 수
        n = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        // 계산해야하는 촌수
        str = new StringTokenizer(br.readLine());
        start = Integer.parseInt(str.nextToken());
        end = Integer.parseInt(str.nextToken());

        // 부모 자식들 간의 관계 개수
        m = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

        family = new boolean[n + 1][n + 1];
        visitied = new boolean[n + 1];      // 방문 여부를 채크한다.
        nums = new int[n + 1];

        // 관계 정보를 저장한다.
        for (int i = 0; i < m; i++) {
            str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());

            family[a][b] = true;
            family[b][a] = true;
        }

		DFS(start, 0);

        if (count == 0) {
            sb.append(-1);
        } else {
            sb.append(count);
        }
        
        System.out.println(sb);
    }

    private static void DFS(int x, int count) {
        visitied[x] = true;

        if (x == end) {
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visitied[i] && family[x][i]) {
                DFS(i, count + 1);
            }
        }

        System.out.println("x - " + x + " count - " + count);
    }  
}