백준 16940 C++

문제에서는 거리가 같은 노드가 여러 개 있다면 어느 방향으로 진행한 것이어도 정답으로 인정하고, 어느 방향으로 진행하더라도 불가능한 경로로 답변한 경우 오답으로 처리하고자 한다.

#include <iostream> // 기본 입출력을 위한 헤더
#include <vector> // 벡터 컨테이너 사용을 위한 헤더
#include <algorithm> // sort 함수 사용을 위한 헤더
#include <queue> // 큐 사용을 위한 헤더

#define MAX 100001 // 상수 정의: 최대 노드 수 + 1

using namespace std;

int n; // 전역 변수로 노드의 수 선언
vector<int> graph[MAX]; // 각 노드에 인접한 노드들을 저장할 벡터 배열
int order[MAX]; // 노드 방문 순서를 저장할 배열
bool visit[MAX]; // 노드 방문 여부를 체크할 배열

int bfs() { // 너비 우선 탐색(BFS) 함수
    queue<int> q; // 탐색할 노드를 저장할 큐
    q.push(1); // 시작 노드(1번 노드)를 큐에 추가
    visit[1] = 1; // 시작 노드를 방문한 것으로 표시
    int expectedOrder = 2; // 다음으로 방문할 노드의 예상 순서

    while (!q.empty()) { // 큐가 빌 때까지 반복
        int curr = q.front(); // 현재 탐색할 노드
        q.pop(); // 큐에서 현재 노드를 제거

        for (auto next : graph[curr]) { // 현재 노드에 인접한 모든 노드를 순회
            if (visit[next]) continue; // 이미 방문한 노드는 건너뜀

            if (!visit[next] && order[next] == expectedOrder) { // 방문하지 않은 노드이며 예상 순서와 일치할 경우
                visit[next] = 1; // 노드를 방문한 것으로 표시
                q.push(next); // 해당 노드를 큐에 추가
                expectedOrder++; // 다음 예상 순서를 업데이트
            } else if (order[next] != expectedOrder) { // 예상 순서와 일치하지 않는 경우
                return 0; // 탐색 실패
            }
        }
    }
    return 1; // 모든 노드를 예상 순서대로 탐색한 경우
}

bool compare(const int& a, const int& b) { // 노드 방문 순서를 비교하는 함수
	return order[a] < order[b];
}

int main() {
    cin >> n; // 노드의 수 입력 받기
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v; // 노드 간의 연결(간선) 정보 입력 받기
        graph[u].push_back(v); // 무방향 그래프이므로 양방향으로 추가
        graph[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        int x; cin >> x; // 방문 순서 입력 받기
        order[x] = i; // 순서 정보를 order 배열에 저장
    }

    for (int i = 1; i <= n; i++) { // 각 노드에 대해
        sort(graph[i].begin(), graph[i].end(), compare); // 인접한 노드를 방문 순서에 따라 정렬
    }

    cout << bfs(); // BFS 함수 호출 후 결과 출력

    return 0;
}