백준 - 특정 거리의 도시 찾기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/18352

[문제 설명]

어느 도시로부터 특정 거리의 있는 도시들을 오름차순으로 출력하시오.

[접근 방법]

시작 도시를 기준으로 BFS하여, 같은 층(같은 거리)에 있는 요소들을 반환하면 된다.

주의해야 할 점은 사이클(시작점과 끝점이 같은 경로)이 있으므로 방문 여부를 체크해줘야 한다는 것과 오름차순으로 결과를 반환해야 한다는 것.

리스트에 넣어서 퀵정렬을 통해 정렬한 후에 반환해줘도 되겠지만, 그것보다는 메모리를 추가적으로 쓰더라도 배열을 따로 만들어서 리턴해주는 게 나아 보여서 그렇게 해줬다.

 

// 리스트를 사용할 경우 아무리 빨라도 정렬의 시간복잡도가 O(Vlog(V))
List<Integer> list = new ArrayList<>();
Collections.sort(list);
list.forEach(idxOfCity -> System.out.println(idxOfCity+1));

// 배열을 사용하는 경우, 모든 노드를 확인하면 되므로 O(V)
boolean[] answer = new boolean[V];
for (int i = 0; i < V; i++) {
	// 정답인 인덱스면 해당 마을 번호를 리턴.
	if (answer[i]) {
    	// 배열의 인덱스는 0부터 시작이므로 +1해서 출력.
    	System.out.println(i+1);
    }
}

 

 

[자바 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 cntOfCities = Integer.parseInt(st.nextToken());
        int cntOfRoads = Integer.parseInt(st.nextToken());
        int neededDistance = Integer.parseInt(st.nextToken());
        int idxOfStartCity = Integer.parseInt(st.nextToken())-1;
        List<Integer>[] listOfRoads = new LinkedList[cntOfCities];
        boolean[] isVisitedCity = new boolean[cntOfCities];

        // 단방향 도로
        for (int i = 0; i < cntOfRoads; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int startCityIndex = Integer.parseInt(st.nextToken())-1;
            int destinationCity = Integer.parseInt(st.nextToken());

            if (listOfRoads[startCityIndex] == null) {
                listOfRoads[startCityIndex] = new LinkedList<>();
            }
            listOfRoads[startCityIndex].add(destinationCity-1);
        }

        // BFS
        Queue<Integer> q = null;
        if (listOfRoads[idxOfStartCity] != null) {
            q = new LinkedList();
            q.offer(idxOfStartCity);
            isVisitedCity[idxOfStartCity] = true;
            int distance = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    int numberOfCity = q.poll();
                    isVisitedCity[numberOfCity] = true;
                    List<Integer> sameDistanceCitys = listOfRoads[numberOfCity];
                    if (sameDistanceCitys != null) {
                        for (int j = 0; j < sameDistanceCitys.size(); j++) {
                            int children = sameDistanceCitys.get(j);
                            // 방문했던 도시면, 추가하지 않음.
                            if (isVisitedCity[children]) {
                                continue;
                            }

                            q.offer(children);
                            isVisitedCity[children] = true;
                        }
                    }
                }
                if (++distance == neededDistance) {
                    break;
                }
            }
        }
        
        boolean[] answer = new boolean[cntOfCities];
        if (q == null || q.size() == 0) {
            System.out.println(-1);
        } else {
            int answerSize = 0;
            while (!q.isEmpty()) {
                int city = q.poll();
                answer[city] = true;
                answerSize++;
            }

            if (answerSize == 0) {
                System.out.println(-1);
            } else {
                int i = 0;
                while (answerSize > 0) {
                    if (answer[i]) {
                        System.out.println(i+1);
                        answerSize--;
                    }
                    i++;
                }
            }
        }
    }
}