99클럽 코테 스터디 10일차 TIL (미들러): [백준][Java] 18352 특정 거리의 도시 찾기 - 실버2

 

문제 보기

https://www.acmicpc.net/problem/18352

 

 

풀이

오늘도 다익스트라 문제가 나왔다.

요즘 자주 보는 것 같다고 생각했는데 내가 챌린지 문제도 같이 풀어서 그런 것 같다.

 

핵심적인 부분은 각 노드까지의 최단거리를 구하는 부분이다.

Queue<Node> queue = new PriorityQueue<>();
int[] dist = new int[N + 1];
boolean[] visited = new boolean[N + 1];

for(int i = 1; i <= N; i++) {
  dist[i] = Integer.MAX_VALUE;
}

queue.add(new Node(X, 0));
dist[X] = 0;
visited[X] = true;

우선 본격적인 탐색을 시작하기 전 단계이다.

우선순위 큐를 만들고 시작 노드를 집어 넣는다.

 

여기서 Node 클래스는 노드 인덱스와 거리로 구성되어 있다.

그리고 우선순위는 거리가 작은 순이다.

 

필연적으로 가까운 순 부터 방문하게 된다는 뜻이다.

이후 같은 노드에 다시 방문해도 최단거리가 아니기 때문에 visited 배열을 만들어 최초 방문이 아닐 경우 넘어가도록 했다.

 

while (!queue.isEmpty()) {
  Node node = queue.poll();

  for (int i = 0; i < graph[node.index].size(); i++) {
    if(!visited[graph[node.index].get(i)]) {
      visited[graph[node.index].get(i)] = true;
      if (dist[graph[node.index].get(i)] > node.dist + 1) {
        dist[graph[node.index].get(i)] = node.dist + 1;
      }
      queue.add(new Node(graph[node.index].get(i), node.dist + 1));
    }
  }
}

본격적으로 탐색하는 부분이다.

이미 dist배열에 저장된 최단거리가 현재 구할 수 있는 최단거리보다 클 경우 갱신한다.

그리고 새 노드를 큐에 집어넣는다.

 

모든 탐색이 끝난 뒤 dist배열을 순회하며 k와 같은 거리를 가진 노드를 찾는다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import org.w3c.dom.Node;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    int X = Integer.parseInt(st.nextToken());

    List<Integer>[] graph = new List[N + 1];
    for(int i = 1; i <= N; i++) {
      graph[i] = new ArrayList<>();
    }
    while (M-- > 0) {
      st = new StringTokenizer(br.readLine());
      graph[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
    }

    Queue<Node> queue = new PriorityQueue<>();
    int[] dist = new int[N + 1];
    boolean[] visited = new boolean[N + 1];

    for(int i = 1; i <= N; i++) {
      dist[i] = Integer.MAX_VALUE;
    }

    queue.add(new Node(X, 0));
    dist[X] = 0;
    visited[X] = true;

    while (!queue.isEmpty()) {
      Node node = queue.poll();

      for (int i = 0; i < graph[node.index].size(); i++) {
        if(!visited[graph[node.index].get(i)]) {
          visited[graph[node.index].get(i)] = true;
          if (dist[graph[node.index].get(i)] > node.dist + 1) {
            dist[graph[node.index].get(i)] = node.dist + 1;
          }
          queue.add(new Node(graph[node.index].get(i), node.dist + 1));
        }
      }
    }
    int count = -1;
    for(int i = 1; i <= N; i++) {
      if(dist[i] == K){
        bw.write(i + "\n");
        count++;
      }
    }
    if(count == -1){
      bw.write(-1 + "");
    }

    bw.flush();
    bw.close();
  }

  static class Node implements Comparable<Node> {
    int index;
    int dist;

    public Node(int index, int dist) {
      this.index = index;
      this.dist = dist;
    }

    @Override
    public int compareTo(Node o) {
      return this.dist - o.dist;
    }
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/18352.%E2%80%85%ED%8A%B9%EC%A0%95%E2%80%85%EA%B1%B0%EB%A6%AC%EC%9D%98%E2%80%85%EB%8F%84%EC%8B%9C%E2%80%85%EC%B0%BE%EA%B8%B0

CodingTest_AutoSave/백준/Silver/18352. 특정 거리의 도시 찾기 at main · MetroDefro/CodingTest_AutoSave