촌수계산

이번 문제는 그래프를 저장하는 두가지 방법 모두 코드로 구현하면서 연습해봤다. 또, 어떤 문제에서 BFS를 사용하고 DFS를 사용하는지 헷갈리긴 한다. BFS는 최소 이동 횟수나 최단 시간이 키워드가 된다.
이번 문제에서는 촌수계산을 할때 가장 가까운 부모 또는 형제부터 최단거리로 찾아야 하기때문에 BFS를 사용했다.

인접행렬 + BFS 형태의 코드

boolean[] visited; 
//boolean type으로 선언하지 않고 간선의 개수를 세기 위해서 int type으로 배열을 선언했다.
int[] dist = new int[n + 1];

start정점에서 i까지 때 필요한 최소 간선의 개수 +1
두 사람의 친척 관계가 전혀 없는 경우 촌수 계산을 할 수 없을 때 return -1

package Graph;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_2644 {
    static int n, m;
    static int target1, target2;
    static int[] answer;
    static int[][] adj;
    static StringTokenizer st;
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        target1 = Integer.parseInt(st.nextToken());
        target2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());

        adj = new int[n + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[a][b] = adj[b][a] = 1;
        }


        answer = new int[n + 1];
        BFS(target1);
        System.out.println(answer[target2]);

    }

    private static void BFS(int start) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            answer[i] = -1;
        }
        queue.add(start);
        answer[start] = 0;

        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int y = 1; y<= n; y++) {
                if (adj[v][y] == 0) continue;
                if (answer[y] != -1) continue;
                queue.add(y);
                answer[y] = answer[v] + 1;
            }
        }


    }

}

인접 리스트 + BFS 코드

package Graph;

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

public class BOJ_2644_list {
    static int n, m, target1, target2;
    static ArrayList<Integer>[] adj;
    static int[] dist;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
      BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        target1 = Integer.parseInt(st.nextToken());
        target2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());

        adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[a].add(b);
            adj[b].add(a);
        }
        dist = new int[n + 1];
        BFS(target1);
        System.out.println(dist[target2]);

    }

    private static void BFS(int start) {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            dist[i] = -1;
        }
        q.add(start);
        dist[start] = 0;

        while (!q.isEmpty()) {
            int x = q.poll();
            for(int y : adj[x]) {
                if(dist[y] != -1) continue; //이미 탐색한 점이면 무시
                q.add(y);
                dist[y] = dist[x] + 1;
            }
        }

    }

}