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

오늘의 학습 키워드

• BFS

문제 - 미들러

특정 거리의 도시 찾기

풀이

import java.util.*;

class Main {
  static int n; // 도시의 수
  static int m; // 도로의 개수
  static int k; // 거리 정보
  static int x; // 출발 도시 번호

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

  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 < graph.get(x).size(); i++) {
        int y = graph.get(x).get(i);

        if (visited[y] == -1) {
          q.offer(y);
          visited[y] = visited[x] + 1;
        }
      }
    }
  }

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

    n = sc.nextInt();
    m = sc.nextInt();
    k = sc.nextInt();
    x = sc.nextInt();

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

    graph = new ArrayList<>();

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

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

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

    bfs(x);

    ArrayList<Integer> answer = new ArrayList<>();

    for(int i = 0; i < visited.length; i++) {
      if(visited[i] == k) answer.add(i);
    }

    if(answer.size() == 0) {
      System.out.println(-1);
    } else {
      for(int ans : answer) {
        System.out.println(ans);
      }
    }
  }
}

• BFS를 응용하여 풀이했습니다.
• 양방향이 그래프 풀이에 익숙해 문제를 제대로 읽지 못하고 단방향에 주의하지 못해 처음에 틀렸습니다.