Java 1976 여행 가자

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

1976번: 여행 가자

---

주요 로직은 다음과 같다.

 

1. 방문해야할 노드를 큐에 넣어준다.

2. 큐에 있는 원소들을 하나씩 poll한 뒤 방문처리를 위한 bool배열을 초기화 해준다.(poll한뒤 큐에 원소가 없는 경우는 모든 노드를 방문했으므로 "YES"를 출력하고 return)

3. poll한 노드와 인접하면서 방문하지 않은 노드에 대해서 하나의 큐를 더 만들어 bfs 탐색을 한다.

4. 인접한 노드와 방문해야할 큐의 peek한 원소의 값이 같을 경우 bool 변수를 이용해 체크해준다.(인접한 노드에 대해서 탐색을 종료하였을때 bool 변수가 false 라면 방문할 수 없는 경우이기에 이를 체크하고 "NO"를 출력하고 return)

5. 노드의 값이 같았을 경우에는 방문이 가능한 경우이므로 다음 원소에서부터 1번부터 다시 반복해준다.

 

---

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

public class Main {

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

        StringTokenizer st;

        int[][] map = new int[n][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());
            }
        }
	//방문해야할 노드의 큐
        Queue<Integer> q = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            q.add(Integer.parseInt(st.nextToken())-1);
        }

        boolean[] visited;

        while(!q.isEmpty()){
            visited = new boolean[n];
            int poll = q.poll();
		//방문해야할 노드가 더 이상 없다면 종료
            if(q.isEmpty()){
                System.out.println("YES");
                return;
            }
		//bfs 탐색을 위한 큐
            Queue<Integer> tq = new LinkedList<>();

            tq.add(poll);

            boolean flag = false;
			//bfs
            while(!tq.isEmpty()){
                int poll1 = tq.poll();
                visited[poll1] = true;
			//둘의 값이 같다면 방문이 가능하므로 탐색 종료
                if(poll1 == q.peek()){
                    flag = true;
                    break;
                }

                for(int i = 0; i < n; i++){
                    if(map[poll1][i] == 1 && !visited[i]){
                        tq.add(i);
                    }
                }
            }
			//방문할 수 없으므로 종료
            if(!flag){
                System.out.println("NO");
                return;
            }
        }
    }
}