반응형
리뷰
노드를 1 ~ N 까지 설정해 줘야 했는데, 0 ~ N - 1까지로 설정해 주고 있었어서 계속 틀렸다.. 근데 왜 예제랑 82% 까지 맞는거지?
문제 풀이
- 도시의 최대 개수는 200개 이므로 nodes 배열을 201의 크기로 초기화 해준다.
- 2중 for문을 통해 인접행렬에 있는 값을 받아오고 1이 입력된 경우 해당 row와 col을 참조하여 Union 처리 해준다, 이때 유니온 파인드를 사용하므로 양방향 간선은 의미 없기에 대각선으로 갈라 싸이클 없이 한쪽 면만 받아와도 된다.
- 이후 쿼리로 오는 노드들을 Find를 통해 루트 노드가 같은지 비교하고 만약 다르다면 break 후 NO를 출력한다. 당연히 break 되지 않았다면 YES를 출력하면 된다.
참고 사항
대부분의 문제에서 0번 노드를 주는 경우는 없기에 항상 문제를 잘 확인해 노드를 0부터 설정할지 1부터 설정할지 잘 생각해 보도록 하자.
정답 코드
#include<iostream>
using namespace std;
int n, m;
int nodes[201];
int Find(int a) {
if (nodes[a] == a) return a;
return nodes[a] = Find(nodes[a]);
}
void Union(int a, int b) {
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return;
nodes[rootB] = rootA;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) nodes[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int path; cin >> path;
if (j >= i && path == 1) Union(i, j);
}
}
int privious; cin >> privious;
int flag = 1;
for (int i = 0; i < m - 1; i++) {
int node; cin >> node;
if (Find(node) != Find(privious)) {
flag = 0;
break;
}
privious = node;
}
if (flag) cout << "YES";
else cout << "NO";
}
728x90
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
백준 21924번 도시 건설 C++ MST, 최소 신장 트리 (0) | 2024.08.13 |
---|---|
백준 1197번 최소 스패닝 트리 C++ MST, 최소 신장 트리 (0) | 2024.08.13 |
백준 1717번 집합의 표현 C++ 유니온 파인드 (0) | 2024.08.13 |
백준 6593번 상범 빌딩 C++ BFS (0) | 2024.08.12 |
백준 1719번 택배 C++ 다익스트라 (0) | 2024.08.11 |