[이코테BOJ] 특정거리의도시찾기_18352.java

 문제

- 백준 문제인 '특정 거리의 도시 찾기_18352'를 이코테에서 문제로 나왔다.

 

- 거리가 1인 N개의 도시

- M개의 간선

- 최단거리 K인 모든 도시 번호 출력, 없으면 -1

- X부터 시작

 

 해설 및 코드

- 거리가 1이므로 BFS로 간단하게 풀 수 있는 문제이다.

- 만약 거리가 1이 아니라면, 다익스트라로 접근하면 된다. 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ특정거리의도시찾기_18352 {
	private static int K;
	private static ArrayList<Integer>[] al;

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

		int N = sc.nextInt();
		int M = sc.nextInt();
		// 거리 정보
		K = sc.nextInt();
		// 출발
		int X = sc.nextInt();

		al = new ArrayList[N + 1];

		for (int i = 0; i < al.length; i++) {
			al[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < M; i++) {
			al[sc.nextInt()].add(sc.nextInt());
		}

		Queue<Integer> q = new LinkedList<>();

		q.add(X);

		int[] check = new int[N + 1];
		while (!q.isEmpty()) {
			int buf = q.poll();

			for (int i = 0; i < al[buf].size(); i++) {
				if (check[al[buf].get(i)] == 0) {
					check[al[buf].get(i)] = check[buf]+1;
					q.add(al[buf].get(i));
				}
			}
		}

		boolean ok = false;
		for (int i = 1; i < check.length; i++) {
			if (check[i] == K && i != X) {
				ok = true;
				System.out.println(i);
			}
		}
		if (!ok)
			System.out.println(-1);

	}

}

- 사람들이 많이 틀리는 이유가 생각하지 못한 반례가 하나 있기 때문이다.

4 5 3 1
1 2
1 3
2 3
2 4
4 1

를 입력하면, 시작도시가 출력으로 나오게 된다. 출력할 때, 시작 도시를 제외하면 정답

 

- 처음엔 다익스트라로 해야하나 싶었는데 DFS/BFS 문제라 BFS로 접근했다.

- 조금 어렵게 생각해서, 미리 queue size를 저장해둔 후, cnt를 queue size를 다 돌았을 때만 cnt를 해줬다. 그렇게 해도 큰 문제는 없을 것 같긴 한데..흠..