백준 - 특정 거리의 도시 찾기(18352) - BFS - Java

1. 문제

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

2. 풀이

최단거리 = BFS 공식을 떠올리도록 하자.

2-1. 풀이1

BFS에서 최단거리 노드가 발견되면 바로 answerList에 넣어주고 continue;를 실행하였다. (이후에 탐색될 노드는 어차피 최단 거리를 넘어갈 것이기 때문이다.)

3-1. 코드 1

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

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());
        
        boolean visit[] = new boolean[N+1];
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        
        for(int i = 0; i <= N; i++){
            list.add(new ArrayList<>());
        }
        
        for(int m = 0; m < M; m++){
            st = new StringTokenizer(br.readLine(), " ");
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            list.get(a).add(b);
        }
        
        Queue<Integer> qX = new LinkedList<>();
        Queue<Integer> qC = new LinkedList<>();
        
        qX.add(X);
        qC.add(0);
        visit[X] = true;
        
        ArrayList<Integer> answerList = new ArrayList<>();
        while(!qX.isEmpty()){
            int x = qX.poll();
            int count = qC.poll();
            
            //if(visit[x]) continue;
            
            if(count == K){
                answerList.add(x);
                continue;
            }
            
            for(Integer n : list.get(x)){
                if(!visit[n]){
                    qX.add(n);
                    qC.add(count+1);
                    visit[n] = true;
                }
            }
        }
        
        if(answerList.size() == 0){
            System.out.println(-1);
        } else{
            Collections.sort(answerList);
            for(Integer a : answerList){
                System.out.println(a);
            }
        }
    }
}

2-2. 풀이 2

이중 ArrayList를 쓰지 않고 배열 안에 ArrayList<>를 삽입하였다. 꼭 이중 ArrayList<>를 쓰지 않고도 좋은 방법인 것 같다.

다만 밑에 최단거리가 K인 노드를 answer이라는 ArrayList에 담아서 정렬하고 있는데, 그렇게 하지 않아도 된다는 점이다.
이미 result[i] == K에서 i가 이미 1번~N번 노드이기 때문에 바로 i를 출력하면 되는 것이다.

3-2. 코드 2

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int M = input.nextInt();
		int K = input.nextInt();
		int X = input.nextInt();
		
		//int map[][] = new int[N+1][N+1];
		int check[] = new int[N+1];
		int result[] = new int[N+1];
		
		ArrayList<Integer> maplist[] = new ArrayList[N+1];
		
		for(int i = 0; i <= N; i++)
		//for(int i = 1; i <= N; i++) -> 이렇게 하면 안된다 ㅎㅎㅎ
			maplist[i] = new ArrayList();
		
		for(int m = 0; m < M; m++) {
			
			int A = input.nextInt();
            int B = input.nextInt();
			maplist[A].add(B);
		}
		
		Queue<Integer> City = new LinkedList<>();
		
		check[X] = 1;
		City.add(X);

		while(!City.isEmpty()) {
			
			int C = City.poll();
			
			for(int i = 0; i < maplist[C].size(); i++) {
				
				int go_city = maplist[C].get(i);
				
				if(check[go_city] == 0) {
					City.add(go_city);
					check[go_city] = 1;
					result[go_city] = result[C] + 1;
				}
			}
		}
		
        /**
        * i번째부터 정렬되어 있는 것이기 때문에 굳이 또 정렬을 할 필요가 없다. 
        * Flag를 두고 result[i] == K이면 그대로 바로 출력하면 된다. (없을 경우 flag = false이므로 -1출력)
        **/
		ArrayList<Integer> answer = new ArrayList<>();
		for(int i = 1; i <= N; i++) {
			//if(check[i] == K)
			if(result[i] == K)
				answer.add(i);
		}
		
		if(answer.size() == 0)
			System.out.println(-1);
		
		else {
			
			Collections.sort(answer);
			for(int a = 0; a < answer.size(); a++) {
				System.out.println(answer.get(a));
			}
		}
	}

}