✈️백준 : 여행가자

긍긍·2025년 10월 21일

알고리즘

목록 보기

23/30

문제

1976번: 여행가자
LV: 골드 4

주어진 도시 $N$ 개와 도시 간의 연결 정보( $N \times N$ 인접 행렬)를 바탕으로, 정해진 여행 계획( $M$ 개의 도시 순서)을 따라 여행하는 것이 가능한지 판별하는 문제

특징: 중간에 다른 도시를 경유하는 것은 자유롭게 허용되며, 같은 도시를 여러 번 방문할 수 있다. 즉, 두 도시가 직접 연결되어 있지 않아도, 경로만 있다면 이동 가능하다.

🔍 입력 및 출력

입력

도시의 수 $N$ (1부터 $N$ 까지 번호)
여행 계획에 속한 도시의 수 $M$
$N$ 개의 줄에 걸쳐 $N \times N$ 크기의 인접 행렬
- 1: 두 도시가 직접 연결됨 (양방향)
- 0: 연결되지 않음
여행 계획에 속한 도시 번호 $M$ 개가 순서대로 주어짐. (도시 번호는 $1$ 부터 $N$ 까지)

출력

여행 경로가 모두 가능하면 YES
여행 경로 중 하나라도 불가능하면 NO

💡 핵심 풀이: BFS (Breadth-First Search)

이 문제는 여행 계획에 포함된 모든 인접한 두 도시 쌍에 대해 "출발지에서 도착지로 이동이 가능한가?"를 확인하는 문제이다.

도시 간 이동은 직통 연결이 아니더라도, 경로만 있다면 가능하므로, 이는 그래프 탐색 알고리즘인 BFS 를 이용하여 풀이할 수 있다.

풀이 전략

여행 계획을 순차적인 경로 쌍으로 분리: 여행 계획 $(C_1, C_2, \dots, C_M)$ 은 $(C_1 \to C_2), (C_2 \to C_3), \dots, (C_{M-1} \to C_M)$ 와 같은 $M-1$ 개의 개별 경로로 나눌 수 있다.
각 경로 쌍의 가능성 확인: 각 경로 쌍 (출발지 $C_i$ , 도착지 $C_{i+1}$ )에 대해 BFS를 수행하여 출발지에서 도착지로 도달 가능한지 확인한다.
최종 판별: 모든 경로 쌍이 가능하다면 YES, 단 하나라도 불가능하다면 NO를 출력한다.

📝 코드 흐름 상세 (Java 기준)

전체 여행 가능 여부를 저장할 tripPossible 변수를 true로 초기화하고, $M-1$ 개의 경로에 대해 반복한다.

1. 경로 쌍 설정 및 BFS 초기화

boolean tripPossible = true; 

// M-1개의 경로 쌍에 대해 반복
for (int sp = 0; sp < M - 1; sp++) {
    boolean isPossible = false;
    int start = plan[sp];        // 현재 경로의 출발지
    int dest = plan[sp + 1];     // 현재 경로의 도착지
    boolean[] visited = new boolean[N]; // BFS용 방문 배열 (N: 도시의 수)

    // ... (BFS 수행)
// ...

2. BFS 탐색 및 가능성 판별

Queue를 사용하여 BFS를 수행

Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    visited[start] = true;

    while (!q.isEmpty()) {
        int curr = q.poll();
        
        // **도착지 도달 확인**
        if (curr == dest) {
            isPossible = true; 
            break; // 현재 경로 쌍은 가능하므로 BFS 종료
        }

        // 인접한 모든 도시 탐색 (N: 도시의 수)
        for (int next = 0; next < N; next++) {
            // 연결되어 있고, 방문하지 않은 도시라면 큐에 추가
            if (board[curr][next] == 1 && !visited[next]) {
                q.offer(next);
                visited[next] = true;
            }
        }
    }
// ...

3. 최종 여행 가능 여부 갱신

하나의 경로라도 불가능하면 전체 여행이 불가능하므로, 즉시 반복문을 종료한다.

if (!isPossible) {
        tripPossible = false;
        break; // 전체 여행 불가능 확정이므로 즉시 반복 종료
    }
}

4. 출력

System.out.println(tripPossible ? "YES" : "NO");

주의할 부분

코드를 작성할 때 실수했던 두 가지 사항이 있다.

배열 크기 혼동: BFS 탐색 시 인접 도시를 확인할 때, 도시의 개수( $N$ )만큼 반복해야 하는데 방문할 여행지 개수(M)만큼 반복함 -> 인덱스 범위 초과 에러
visited 배열 처리: BFS는 방문 배열(visited) 처리 필수

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class backjoon_1976_여행가자 {
	public static void main(String[] args) throws IOException {
		// System.setIn(new FileInputStream("src/input.txt")); // 파일 입출력 시 주석 해제

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine()); // 도시의 수
		int M = Integer.parseInt(br.readLine()); // 여행 계획에 속한 도시의 수

		int[][] board = new int[N][N];
		StringTokenizer st;

		// 인접 행렬 입력 받기
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int[] plan = new int[M];
		// 여행 계획 입력 받기 (도시 번호 1-based -> 0-based 인덱스로 변경)
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			plan[i] = Integer.parseInt(st.nextToken()) - 1; 
		}

		boolean tripPossible = true;
        // M-1개의 순차적인 경로 쌍에 대해 BFS 수행
		for (int sp = 0; sp < M - 1; sp++) {
			boolean isPossible = false;

			int start = plan[sp];
			int dest = plan[sp + 1];
			boolean[] visited = new boolean[N]; // 경로 쌍마다 방문 배열 초기화

			Queue<Integer> q = new LinkedList<>();
			q.offer(start);
			visited[start] = true;

			// BFS 시작
			while (!q.isEmpty()) {
				int curr = q.poll();
                
				// 목적지에 도달하면 현재 경로 쌍은 가능
				if (curr == dest) {
					isPossible = true;
					break;
				}

				// 인접한 모든 도시(N개)에 대해 탐색
				for (int next = 0; next < N; next++) {
                    // 직접 연결되어 있고, 아직 방문하지 않은 도시인 경우
					if (board[curr][next] == 1 && !visited[next]) {
						q.offer(next);
						visited[next] = true;
					}
				}
			}
            
            // 현재 경로 쌍이 불가능하면 전체 여행도 불가능
			if (!isPossible) {
				tripPossible = false;
				break;
			}
		}

		System.out.println(tripPossible ? "YES" : "NO");
	}
}