[백준/JAVA] 1976번: 여행 가자

백준

[백준/JAVA] 1976번: 여행 가자

찌끄랭이 2023. 2. 21. 16:35

문제 보러가기

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

[문제 풀이]

List에 노드간 연결이 되어있다면 연결을 저장하고, 연결이 되어있지 않거나 자기 자신이라면 저장하지 않았다.

출발 지점을 방문하게 될 노드 중 한가지로 선택하고 BFS를 통해 갈 수 있는 노드를 배열에 표시하였다.

배열이 완성된다면 방문하게 될 노드 중 표시되어있지 않다면 "NO", 모두 표시 되어있다면 "YES"를 출력한다.

[코드]

import java.io.*;
import java.util.*;

class Main {
    static int N, M;
    static List<List<Integer>> lists = new ArrayList<>();
    static int[] connect; //방문할 수 있는 노드

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        connect = new int[N + 1];
        for (int i = 0; i <= N; i++) lists.add(new ArrayList<>());

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int node = Integer.parseInt(st.nextToken());
                if (j == i) continue;
                if (node == 1) lists.get(i).add(j); //자기자신이 아니고 연결이 되어있다면 저장 이때, i는 출발지점, j는 목적지이다.
            }
        }

        int[] visit = new int[M]; //방문해야할 노드 정보
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            visit[i] = Integer.parseInt(st.nextToken());
        }

        connect[visit[0]] = 1;
        BFS(visit[0]);

        boolean check = true;
        for (int i = 0; i < M; i++) {
            if (connect[visit[i]] != 1) {
                check = false;
                break;
            }
        }

        if (check) System.out.println("YES");
        else System.out.println("NO");
    }

    public static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        boolean[] visited = new boolean[N + 1];

        while (!queue.isEmpty()) {
            int temp = queue.poll();

            if (visited[temp]) continue;
            visited[temp] = true;

            List<Integer> list = lists.get(temp);
            for (int A : list) {
                if (visited[A]) continue;
                connect[A] = 1;
                queue.add(A);
            }
        }
    }
}

저작자표시 (새창열림)