문제

문제 링크

문제 접근

  • 여행 경로를 순서대로 진행하다가 다음 위치로 이동하는 것이 불가능한지 여부를 확인해야한다.
  • 그 때 필요한 것은 둘 사이에 경로가 있는가를 확인해야한다.
  • 그를 위해 플로이드 와샬 알고리즘을 이용해서 미리 모든 여행지에서 모든 여행지로 갈 수 있는 경로를 찾아놓는다.
  • 그 후 여행지를 둘씩 확인하면서 경로가 있는지 봐준다.

코드

#include <cstdio>

int main(){
    int n, m, arr[201][201];
    scanf("%d %d", &n, &m);
    for(int i = 1; i < n + 1; i++){
        for(int j = 1; j < n + 1; j++)scanf("%d", &arr[i][j]);
        arr[i][i] = 1;
    }
    for(int k = 1; k < n + 1; k++){
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < n + 1; j++){
                if(arr[i][k] && arr[k][j])arr[i][j] = 1;
            }
        }
    }
    int v1, v2;
    int ans = 1;
    scanf("%d", &v1);
    for(int i = 0; i < m - 1; i++){
        scanf("%d", &v2);
        if(!arr[v1][v2] && !arr[v2][v1])ans = 0;
        v1 = v2;
    }
    if(ans)printf("YES");
    else printf("NO");
}

느낀점

  • 플로이드 와샬 참 좋다..ㅎㅎ