[백준] 1976: 여행 가자 JAVA

접근

바로 이전 게시글에서 풀었던 경로 찾기 문제와 매우 유사하다. 여행 동선을 체크할 때 중간에 여러 도시를 지나가도 되고 동일한 도시를 여러 번 방문해도 된다는 얘기는, 결국 A > B 도시로 이동 가능한 경로가 있는가만 확인하면 된다. 어차피 양방향 그래프이기 때문에 나는 스택에 저장해두고 뒤쪽 도시부터 반대 방향으로 확인했다. 

처음에 75%에서 틀렸다는 결과가 나왔는데, 질문 게시판에서 반례를 찾았다. 여행 계획이 A > A, 즉 같은 도시로 이동할 수도 있는거다. 문제에서 연결 정보를 입력받을 때에는 같은 도시에 대한 정보는 포함되어 있지 않으므로 이 부분이 누락됐던 것 같다. 그래서 if(i == j) graph[i][j] = 1 조건을 추가해주었다. 

 

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] graph = new int[n+1][n+1];
        
        for(int i = 1;i <= n;i++){
            st = new StringTokenizer(br.readLine());
            
            for(int j = 1;j <= n;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                if(i == j) graph[i][j] = 1;
            }
        }

        // 여행 계획
        st = new StringTokenizer(br.readLine());
        Queue<Integer> q = new LinkedList();
        while(st.hasMoreTokens()){
            int cur = Integer.parseInt(st.nextToken());
            q.add(cur);
        }

        // 플로이드 워셜 알고리즘
        solve(graph, n);

        // 결과 출력
        Boolean possible = true;
        int cur = q.poll();
        while(!q.isEmpty()){
            int next = q.poll();
            
            if(graph[cur][next] == 0){
                possible = false;
                break;
            }
            cur = next;
        }

        String answer = possible ? "YES" : "NO";
        System.out.println(answer);
    }

    static void solve(int[][] graph, int n){
        for(int k = 1;k <= n;k++){
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= n;j++){
                    if(graph[i][k] == 0 || graph[k][j] == 0) continue;  // 양수 길이 없음
                    graph[i][j] = 1;                    
                }
            }
        }
    }
}