[99클럽 코테 스터디] 8일차

오늘의 학습 키워드

• BFS

문제 - 미들러

촌수 계산

풀이

import java.util.*;

class Main {
  static int n;
  static int a, b;
  static int m;

  static ArrayList<ArrayList<Integer>> list;
  static int[] visited;

  static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    visited[start] = 0;

    while(!q.isEmpty()) {
      int x = q.poll();

      for(int i = 0; i < list.get(x).size(); i++) {
        int y = list.get(x).get(i);

        if(visited[y] == -1) { // 방문한 적이 없다면 
          visited[y] = visited[x] + 1;
          q.offer(y);
        }
      }
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    a = sc.nextInt();
    b = sc.nextInt();
    m = sc.nextInt();

    list = new ArrayList<>();
    visited = new int[n + 1];
    Arrays.fill(visited, -1);

    for(int i = 0; i <= n; i++) {
      list.add(new ArrayList<Integer>());
    }

    for(int i = 0; i < m; i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();

      list.get(x).add(y);
      list.get(y).add(x);
    }

    bfs(a);

    System.out.println(visited[b] == -1 ? -1 : visited[b]);
  }
}

• BFS를 이용하여 풀었습니다.
• 인접한 노드 하나를 탐색할 때마다, 1촌씩 증가해줍니다.