[백준] 18352번: 특정 거리의 도시 찾기

 

문제 파악

- 출발점 X에서 특정 거리 K가 걸리는 노드들을 체크하고 마지막에 출력해주기

 

<알고리즘 분류>
-BFS

 

접근 방법

-BFS사용해 최단 거리 카운트하기

-출발점은 하나이고 단일로 연결 된 노드를 타고 가서 거리를 카운트

-거리는 모두 1로 통일(별도의 가중치 없음 파악)

-visited를 int[]로 변형 활용하여(토마토 문제처럼) 노드마다 '출발점에서 얼마나 걸렸는지' 적재해주기

 

 

 

 

 

코드 구현

package org.server;
import java.io.*;
import java.util.*;

public class Main {
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        ArrayList<Integer>[] graph = new ArrayList[N+1];
        //System.out.println(K);

        for(int i=1;i<=N;i++){
            graph[i] = new ArrayList<>();
        }
        
        
        for(int j=0;j<M;j++){
            st = new StringTokenizer(br.readLine());
            int fromNode = Integer.parseInt(st.nextToken());
            int toNode = Integer.parseInt(st.nextToken());
            graph[fromNode].add(toNode);//단방향
        }
        int[] visited = new int[N+1];
        Arrays.fill(visited, -1);//미방문 체크 위해 -1로 초기화
        
        ArrayDeque<Integer> que = new ArrayDeque<>();
        ArrayList<Integer> answer = new ArrayList<>();
        que.add(X);
        visited[X]=0;//가장 처음 출발지점은 0으로 초기화 -> 타고타고 갈거라서 여기서만 하면 됨
        while (!que.isEmpty()) {
            int curr = que.poll();
            
            for(int next:graph[curr]){
                if(visited[next]==-1){
                    que.add(next);
                    visited[next]=visited[curr]+1;//포인트
                }
                
            }
        }
        for(int i=1;i<=N;i++){
            if(visited[i]==K){
                answer.add(i);
            }
        }
        if(answer.size()==0){
            System.out.println(-1);
        }else{
            Collections.sort(answer);
            for(int x:answer){
                System.out.println(x);
            }
            
        }
        
    }
        
}

 

 

 

배우게 된 점

-visited[next] = visited[curr]+1 //현재보다 한 칸 더 간 것을 이렇게 체크해준다.

-풀이를 좀 찾아봤는데, 푸는 방법은 제 각기고 자율의 영역임을 배움