[백준] 1976: 여행가자 (BFS, 그래프탐색) - JAVA

골드 3~4 무작위 풀이

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

 

 

 

너무 오랜만에 문제풀이 블로그를 작성한다 ! (사실 오랜만에 문제를 풀었다)

지피티, 구글링을 안 하고 하려니까 오래 걸리는 문제들도 많고 ,,, 이래저래 할거도 많아서 소홀해진듯 다시 매일 풀어야겠다

 

---

 

# 문제

 

# 필요개념

처음 문제를 봤을 땐 복잡하게 느껴졌다. 현재 시작점에서 다음 경로까지 길이 있는지 탐색하고, 있으면 또 다음 경로까지 길이 있는지 탐색하고.... 같은 도시를 여러번 갈 수도 있다고 하니 방문여부 체크는 불필요 할 거 같고,, 안 하자니 시간이 오래걸릴 거 같아서 고민이 되었다.

 

그런데 끄적이면서 생각해보니, 그냥 시작점에서 연결된 모든 지역을 탐색하고 내가 가려는 도시가 첫 도시와 연결되어있지 않으면 갈 수 없는 거 아닌가? 라고 생각하니 문제가 굉장히 쉬워졌다.

 

즉, 첫 도시와 연결이 되어있는가 여부만 살피면 될 일이었다 

 

탐색방법

그래프 탐색 방법은 DFS, BFS가 있고 어차피 전체탐색을 해야하고, 최대 깊이가 어느정도인지 알 길도 없으니 BFS를 이용해보기로 했다. 여행 시작 도시를 시작점으로 잡아서 전체 탐색을 시작한다.

 

탐색하면서 방문한 지역은 방문배열을 통해 업데이트 해준다.

 

 

이후 여행해야하는 도시를 담아둔 배열을 반복문으로 돌린다. 해당 도시를 방문하지 않았다면 false를 리턴, 다 방문했다면 true를 리턴한다.

 

이 문제에서는 여행 경로를 출력하지 않고 가능 여부만 물어봤기 때문에 간단하게 풀 수 있었던 거 같다.

만약 경로까지 출력해야했다면 조금 더 까다롭지 않았을까 싶다 😶‍🌫️

 

# Code

요즘 주석 작성을 습관화 하려 하는데 문제푸는데 참 도움이 된

package Baekjun;

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


// 1976
public class Main {

    static List<List<Integer>> graph = new ArrayList<>();
    static int[] trips;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 도시 수
        int M = Integer.parseInt(br.readLine()); // 여행 계획에 속한 도시 수
        StringTokenizer st;

        int[][] map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        // 배열 기반으로 양방향 그래프 만들기
        makeGraph(map);

        // 탐색
        boolean ans = search();
        System.out.println(ans ? "YES" : "NO");

    }
    /*
    * 시작 노드 기준 전체탐색 (연결이 되어있다면 다른 곳을 경유해서라도 갈 수는 있음)
    * -> 가야하는 여행경로 중 시작노드와 연결되지 않은 노드가 하나라도 있으면 false
    * */
    private static boolean search() {
        int start = trips[0];
        boolean[] isVisit = new boolean[N + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            Integer city = queue.poll();
            isVisit[city] = true;
            for (int next : graph.get(city)) {
                if (!isVisit[next]) {
                    queue.add(next);
                }
            }
        }

        for (int trip : trips) {
            if (!isVisit[trip]) return false;
        }
        return true;
    }

    private static void makeGraph(int[][] map) {
        // 리스트 속 리스트 생성
        for (int i = 0 ; i <= N ; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 생성
        for (int i = 1 ; i <= N ; i++) {
            for (int j = i ; j <= N ; j++) {
                if (map[i][j] == 1) {
                    graph.get(i).add(j);
                    graph.get(j).add(i); // 양방향
                }
            }
        }
    }
}

 

# 결과