[백준][1976] 여행 가자

이 포스트는 백준 사이트의 여행 가자 문제 풀이입니다.

문제

해결 과정

이 문제는 플로이드 워셜 알고리즘을 사용해 풀 수 있는 문제입니다.

여행 경로별로 비용을 계산할 때, 모든 여행 지점에서 또다른 모든 지점까지의 경로를 구하는 플로이드 워셜 알고리즘을 사용하면 문제를 쉽게 풀 수 있습니다.

플로이드 워셜 알고리즘을 사용하기 전 2차원 배열을 만들 때,
배열 중 행과 열이 같은 부분((1, 1), (2, 2), … , (N, N))은 사용하지 않는 값으로 초기화하고
문제에서 이동간 방향성이 없으므로 양방향 모두 같은 비용으로 초기화합니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> edge(N, vector<int>(N, 1000));
    for(int row = 0; row < N; ++row) {
        for(int col = 0, temp; col < N; ++col) {
            cin >> temp;

            if(temp != 0) {
                edge[row][col] = temp;
                edge[col][row] = temp;
            }
            if(row == col) {
                edge[row][col] = 0;
            }
        }
    }

    vector<int> plan(M, 0);
    for(int i = 0; i < M; ++i) {
        cin >> plan[i];
    }

    for(int k = 0; k < N; ++k) {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
            }
        }
    }


    string answer = "YES";
    int start = plan[0] - 1;
    for(int end : plan) {
        if(edge[start][end - 1] == 1000 || edge[end - 1][start] == 1000) {
            answer = "NO"; 
            break;
        } else {
            answer = "YES";
        }
    }
    cout << answer;
    
    return 0;
}

실행 결과