[백준] 1976번 : 여행 가자 - 자바(JAVA)

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

1976번: 여행 가자

 

문제 해석

N개의 도시가 존재하고 두 도시 사이에 길이 있을 수도 없을 수도 있습니다. 

여행 경로가 가능한지 탐색하고자 합니다.

 

만약 도시가 5개 존재하고 A-B, B-C, A-D, B-D, E-A의 길이 존재합니다.

 

이를 그림으로 도식화 하면 다음과 같습니다.

위의 그림 예시에서는 모든 도시가 연결되어있기 때문에 어떤 여행계획이든 가능합니다.

 

 

 

문제 풀이 전 설계

위의 예시에서 봤듯이 모든 도시가 연결되어 있다면 어떠한 여행경로든 문제 없습니다.

주의해야 할 점은 외딴 섬처럼 떨어져 있는 도시를 주의해야 합니다.

 

결국 BFS를 통해 각 도시들을 Grouping 하여 서로 연결된 도시들을 표시하고 마지막 줄에 주어지는 여행 계획을 수행할 수 있는지 확인합니다.

 

이후에 여행 계획을 수행하면서 그룹을 순회하면서 모든 여행 계획에 주어진 도시들이 한 그룹에 속하는지 검사합니다.

 

코드

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

public class Main_1976_여행가자 {

    static List<HashSet<Integer>> groupingState = new ArrayList<>();
    static List<ArrayList<Integer>> cities = new ArrayList<>();
    static List<Integer> planCities = new ArrayList<>();
    static boolean[] visited;
    static int index;

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


        for (int i = 0; i <= cityCount; i++) {
            cities.add(new ArrayList<>());
        }

        StringTokenizer st = null;
        for (int i = 1; i <= cityCount; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= cityCount; j++) {
                int state = Integer.parseInt(st.nextToken());
                if (isLink(state)) {
                    cities.get(i)
                          .add(j);
                    cities.get(j)
                          .add(i);
                }
            }
        }

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < planCount; i++) {
            planCities.add(Integer.parseInt(st.nextToken()));
        }

        //입력값으로 부터 도시 연결
        visited = new boolean[cityCount + 1];
        grouping();

        String result = "NO";
        for (HashSet<Integer> group : groupingState) {
            int size = planCities.size();
            int count = 0;
            for (Integer planCity : planCities) {
                if (group.contains(planCity)) {
                    count++;
                }
            }
            if (count == size) {
                result = "YES";
            }
            count = 0;
        }

        System.out.println(result);

    }

    private static void grouping() {
        int size = cities.size();

        for (int i = 1; i < size; i++) {
            if (visited[i]) {
                continue;
            }

            BFS(index++, i);

        }
    }

    private static void BFS(int index, int curCity) {
        //새로운 그룹할당
        groupingState.add(new HashSet<>());

        //현재그룹에 curCity 추가
        HashSet<Integer> curGroup = groupingState.get(index);

        //bfs
        Queue<Integer> bfsQ = new LinkedList<>();
        bfsQ.add(curCity);
        visited[curCity] = true;
        while (!bfsQ.isEmpty()) {
            Integer cur = bfsQ.poll();
            curGroup.add(cur);

            List<Integer> cityLinkInfo = cities.get(cur);
            for (Integer linkedCity : cityLinkInfo) {
                if (visited[linkedCity]) {
                    continue;
                }
                visited[linkedCity] = true;
                bfsQ.add(linkedCity);
                curGroup.add(linkedCity);
            }
        }
    }

    private static boolean isLink(int state) {
        return state == 1 ? true : false;
    }
}