1번부터 N번까지의 도시와 M개의 단방향 도로가 존재하고, 모든 도로의 거리는 1인 도시가 있다.
도시 X로부터 출발해 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하시오(출발 도시 X에서 출발 도시 X로 가는 최단거리는 항상 0이다).
예를 들어 N = 4, K = 1, X = 1일 때 다음과 같이 그래프가 구성돼 있다고 가정해 보자.
이때 1번 도시에서 출발해 도달할 수 있는 도시 중 최단 거리가 1인 도시는 2번과 3번 도시다. 4번 도시는 최단 거리가 2이므로 출력하지 않는다.
(시간 제한 2초)
입력
1번째 줄에 도시의 개수(N), 도로의 개수(M), 거리 정보(K), 출발 도시의 번호(X)가 입력된다.(2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N). 이후 M개의 줄에 걸쳐 2개의 자연수 A, B가 공백으로 구분돼 주어진다. A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 뜻이다(1 ≤ A, B ≤ N). 단, A와 B는 같을 수 없다.
출력
X로부터 출발해 도달 가능한 도시 중 최단 거리가 K인 모든 도시의 번호를 1줄에 1개씩 오름차순으로 출력한다. 해당하는 도시가 1개도 존재하지 않으면 -1을 출력한다.
예제 입력
4 4 2 1 // 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호
1 2
1 3
2 3
2 4
예제 출력
4
1단계 - 문제 분석하기
모든 도로의 거리가 1이므로 가중치 없는 인접 리스트로 그래프를 표현할 수 있다.
도시의 개수가 300,000, 도로의 최대 크기가 1,000,000이므로 BFS 탐색을 수행하면 시간 복잡도 안에서 문제를 해결할 수 있다.
2단계 - 손으로 풀어 보기
1 인접 리스트로 도시와 도로 데이터 그래프를 구현한다.
2 BFS 탐색 알고리즘으로 탐색을 수행하면서 각 도시로 가는 최단 거릿값을 방문 배열에 저장한다.
최초 방문 도시에는 이동하지 않았으므로 방문 배열에 0을 저장한다.
이후 방문하는 도시는 이전 도시의 방문 배열값 + 1을 방문 배열에 저장하는 방식으로 이동 거리를 저장한다.
3 탐색 종료 후 방문 배열에 값이 K와 같은 도시의 번호를 출력한다.
3단계 - sudo코드 작성하기
N(노드 개수) M(에지 개수) K(목표 거리) X(시작점)
answer(정답 리스트)
A(그래프 데이터 저장 인접 리스트) visited(방문 거리 저장 배열)
for(N의 개수만큼 반복)
A 인접 리스트의 각 ArrayList 초기화
for(N의 개수만큼 반복)
A 인접 리스트에 그래프 데이터 저장
visited 배열 초기화
BFS(X) 실행
for(N의 개수만큼 반복)
방문 거리가 K인 노드의 숫자를 정답 배열에 더하기
정답 배열 오름차순 정렬해 출력하기
BFS
{
큐 자료구조에 출발 노드 더하기(add)
visited 배열에 현재 노드 방문 기록
while(큐가 빌 때 까지)
{
큐에서 노드 가져오기(poll)
가져온 노드 출력
현재 노드와 연결된 노드 중 방문하지 않은 노드로
큐에 데이터 삽입(add)하고 visited 배열에 방문 거리 기록(이전 노드 방문 거리 + 1)
}
}4단계 - 코드 구현하기
import java.util.*;
public class Q46 {
static int[] visited;
static ArrayList<Integer>[] A;
static List<Integer> answer;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int X = sc.nextInt();
A = new ArrayList[N + 1];
answer = new ArrayList<>();
for(int i = 1; i <= N; i++)
A[i] = new ArrayList<>();
for(int i = 0; i < M; i++){
int S = sc.nextInt();
int E = sc.nextInt();
A[S].add(E);
}
visited = new int[N + 1];
for(int i = 0; i <=N; i++){
visited[i] = -1;
}
BFS(X);
for(int i = 0; i <= N; i++){
if(visited[i] == K)
answer.add(i);
}
if(answer.isEmpty())
System.out.println("-1");
else{
Collections.sort(answer);
for(int i : answer)
System.out.println(i);
}
}
public static void BFS(int Node){
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(Node);
visited[Node]++;
while (!queue.isEmpty()){
int now_Node = queue.poll();
for(int i : A[now_Node]){
if(visited[i] == -1){
visited[i] = visited[now_Node] + 1;
queue.add(i);
}
}
}
}
}
- Do it! 알고리즘 코딩테스트 자바 편
