백준 - 상근이의 여행(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

모든 나라를 도는 가장 적은 비행기 종류 수

[접근 방법]

그래프 이론 카테고리를 보고 푸는 문제라서, 바로 BFS DFS가 떠오른 문제다.

모든 도착지에 최단거리가 정답이므로 BFS를 골랐다.

방문 여부는 LinkedList를 사용했고 시간복잡도는 O(모든 정점의 개수+간선의 개수)

=> O(모든 나라의 개수 + 모든 나라의 개수-1) => O(N+N-1) => O(N)이 될 듯하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class HwangInGyu {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfTestcases = Integer.parseInt(br.readLine());

        // for문 반복 한 번에 테스트 케이스 1개씩
        for (int noOfTestcase = 1; noOfTestcase <= cntOfTestcases; noOfTestcase++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            List<Integer>[] map = new LinkedList[N];

            int head = 0;
            // 연결 여부처리
            for (int noOfM = 1; noOfM <= M; noOfM++) {
                st = new StringTokenizer(br.readLine(), " ");
                int startCity = Integer.parseInt(st.nextToken()) - 1;
                int endCity = Integer.parseInt(st.nextToken()) - 1;
                head = startCity;

                if (map[startCity] == null) {
                    map[startCity] = new LinkedList();
                }
                map[startCity].add(endCity);

                if (map[endCity] == null) {
                    map[endCity] = new LinkedList();
                }
                map[endCity].add(startCity);
            }

            int distance = 0;
            boolean[] isVisited = new boolean[N];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(head);
            isVisited[head] = true;

            while (!queue.isEmpty()) {
                int noOfCountry = queue.poll();
                for (int noOfNextCity : map[noOfCountry]) {
                    if (!isVisited[noOfNextCity]) {
                        queue.offer(noOfNextCity);
                        isVisited[noOfNextCity] = true;
                        distance++;
                    }
                }
            }

            System.out.println(distance);
        }
    }
}

 

[내 답안 수정하기]

후에 답을 봤는데, 사실 나라의 총 개수 -1이 답이다.

조건에서 모든 나라를 갈 수 있다는 사실이 있고, 이는 모든 그래프가 연결되어 있다는 뜻이다.

그래프 이론으로 보고 풀어서 생각조차 못했는데 기발한 생각같다. 발상의 전환이 필요하다.