반응형
floyd warshell로 푼 문제였습니다.
풀이방법
1. i -> k로 갈 수 있고 k -> j로 갈 수 있다면 i -> j로도 갈 수 있기 때문에 입력받은 인접행렬을 갱신해줍니다.
2. 여행코스를 확인하면서 갈수 없으면 no, 강 수 있으면 yes를 출력해줍니다.
Code
#include <bits/stdc++.h>
using namespace std;
int n,m,graph[201][201];
vector<int>course;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1,x; j <= n; j++){
cin >> graph[i][j];
}
graph[i][i] = 1;
}
while(m--){
int x;
cin >> x;
course.push_back(x);
}
sort(course.begin(),course.end());
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(graph[i][k] && graph[k][j]){
graph[i][j] = 1;
}
}
}
}
int flag = 0;
for(int i = 0; i < course.size() - 1; i++){
if(!graph[course[i]][course[i+1]] && !graph[course[i+1]][course[i]]) flag = 1;
}
if(flag) cout << "NO";
else cout << "YES";
}
'Algorithm > Floyd Warshell' 카테고리의 다른 글
(C++) - 백준(BOJ) 2458번 : 키 순서 (0) | 2021.07.13 |
---|---|
(C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 합승 택시 요금 (0) | 2021.06.12 |
(C++) - 백준(BOJ) 11404번 : 플로이드 (0) | 2021.04.19 |
(C++) - 프로그래머스(고득점 kit - 그래프) : 순위 (0) | 2021.04.07 |
(C++) - 백준(BOJ) 1058번 : 친구 (0) | 2021.03.27 |