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

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

 

푸는방법이 딱히 떠오르지 않아서 야매?같은 방법으로 풀었는데 의외로 쉽게 풀렸던 문제

 

유니온 파인드를 쓰는게 효율적일꺼같았지만 생각이 나지 않아서 그냥 bfs방식으로 풀었다.

 

또한 길에 대한 정보도 리스트로 관리하는게 더 효율적일꺼같았지만 그냥 문제에서 주어지는 대로 빠르게 풀었다.

 

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

public class Main {
    public static int N, M;
    public static int[][] map;
    public static int[] road, visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        map = new int[N][N];
        road = new int[M];
        visited = new int[N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            road[i] = Integer.parseInt(st.nextToken()) - 1;
        }

        int start = road[0];
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        while(!q.isEmpty()){
            int cur = q.poll();
            if(visited[cur] == 1) continue;
            visited[cur] = 1;
            for(int i = 0; i < N; i++){
                if(map[cur][i] == 1 && visited[i] == 0){
                    q.offer(i);
                }
            }
        }

        for(int i = 1; i < M; i++){
            if(visited[road[i]] == 0) {
                System.out.println("NO");
                System.exit(0);
            }
        }
        System.out.println("YES");
    }
}

 

 

풀긴 풀었지만 입력의 수가 늘어나면 시간초과가 날꺼 같아서 유니온 파인드로도 풀어보았다.

 

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

public class Main {
    static int N, M;
    static int[] rank, parent;

    static int find(int x){
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return;

        if(rank[a] > rank[b]) parent[b] = a;
        else if(rank[a] < rank[b]) parent[a] = b;
        else{
            parent[a] = b;
            rank[b]++;
        }

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

        parent = new int[N];
        rank = new int[N];
        for(int i = 0; i < N; i++) parent[i] = i;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                int v = Integer.parseInt(st.nextToken());
                if(v == 1) union(i, j);
            }
        }

        st = new StringTokenizer(br.readLine());
        int first = Integer.parseInt(st.nextToken()) - 1;
        int root = find(first);

        for(int i = 1; i < M; i++){
            int city = Integer.parseInt(st.nextToken()) - 1;
            if(find(city) != root){
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }
}

 

 

 

시간 차이가 그렇게 많이 나진 않는다.