19352: 특정 거리의 도시 찾기 (JAVA)

18352번: 특정 거리의 도시 찾기

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

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

코드 설명

• graph : 그래프 생성용

  graph = new ArrayList<>();
  for(int i =0; i<=n; i++){
      graph.add(new ArrayList<>());
  }
  for(int i=0; i<m; i++){
  		st = new StringTokenizer(br.readLine());
  		int first = Integer.parseInt(st.nextToken());
  		int second = Integer.parseInt(st.nextToken());
  		graph.get(first).add(second);
  

• dist : 거리만 담은 list

  //거리만 담은 list생성
  int[] dist = new int[n+1];
  for(int i =0; i<dist.length; i++){
  		dist[i] = Integer.MAX_VALUE; //모든 도시간 거리를 INF로 시작
  }
  dist[x] = 0 //단, 시작 도시는 거리 0

• queue : 그래프들의 노드들을 순서대로 담는 큐

  └ 이 문제에서는 굳이 PriorityQueue를 쓰지 않아도 됨을 확인하여 일반 큐로 작성하였다.

  //PQ생성
  pq = new LinkedList<int[]>();
  pq.add(new int[] {x,0});
  
  while(!pq.isEmpty()){
  int[] target = pq.poll();
  int idx = target[0]; //1 - 2 - 3
  
  for(int v : graph.get(idx)){ //2,3 //3,4 // 0 //0
  		if(dist[v] > dist[idx] + 1){
  				dist[v] = dist[idx] + 1;
          pq.add(new int[] {v,dist[v]});
       }
  	}
  }

---

문제풀이 (그림ver)

해당 문제를 풀때 처음에 손으로 그리며 문제를 이해했다.

2번째 사진이 정리된 버전이니 코드를 확인할 때 참고

---

전체코드

import java.io.*;
import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static Queue<int[]> pq;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        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()); //출발 도시의 번호

        //그래프생성
        graph = new ArrayList<>();
        for(int i =0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            graph.get(first).add(second);
        }

        //거리만 담은 list생성
        int[] dist = new int[n+1];
        for(int i =0; i<dist.length; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[x] = 0;

        //PQ생성
        pq = new LinkedList<int[]>();
        pq.add(new int[] {x,0});

        while(!pq.isEmpty()){
            int[] target = pq.poll();

            int idx = target[0]; //1 - 2 - 3
            int dst = target[1]; //0 - 1 - 1


            for(int v : graph.get(idx)){ //2,3 //3,4 // 0 //0
                if(dist[v] > dist[idx] + 1){
                    dist[v] = dist[idx] + 1;
                    pq.add(new int[] {v,dist[v]});
                }
            }
        }
        int answer = 0;
        for(int i =0; i<dist.length;i++){
            if(dist[i] == k){
                System.out.println(i);
                answer++;
            }
        }
        if(answer == 0){
            System.out.println(-1);
        }

    }
}

---

고찰

백준의 유명한 다익스트라 문제이다. 문제를 풀기 전, 다익스트라에 대한 개념을 확실히하고 풀기를 추천한다.

실버II 문제임에도 거리가 1이고, PrirorityQueue를 쓰지 않아도 된다는 점에서 수월하게 해결 할 수 있었던 문제이다.

해당 문제를 BFS로도 푸는 풀이를 봤는데,, 다음에 다시 풀어봐야겠다.

Uploaded by N2T