[Week1]BOJ_2644

カウント
この問題はコードでグラフィックを格納する2つの方法を実現した.また,どのような問題でBFSとDFSを使うかは少し混同している.BFSの最小移動回数または最短時間がキーワードとなる.
この問題では,世代を計算する際に最も親しい親や兄弟から始め,最短距離で見つけるためBFSを用いた.
隣接行列+BFS形式のコード

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

start頂点からiまで必要な最小幹線数+1
2人に全く親戚関係がなければ、世代を計算できない場合は-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;
            }
        }

    }

}