[LeetCode] 1743. Restore the Array From Adjacent Pairs

https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description/

Restore the Array From Adjacent Pairs - LeetCode

leetcode - Restore the Array From Adjacent Pairs

문제 유형 : DFS / BFS

문제 난이도 : Medium

 

 

문제

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

 

중복이 없는 n개의 정수배열 nums가 있다. 그러나 당신은 그걸 잊어버렸다.

그러나, 당신은 nums의 요소들의 인접한 쌍은 알고 있다.

당신은 2차원 정수배열 adjacentPairs가 n-1개 있다.

adjacentParis의 요소인 [u_i, v_i]는 서로 인접해있음을 의미한다. 순서는 의미 없다.

기존의 정수배열 nums를 다시 만들어서 반환하시오. 여러 가지가 나오지만, 그 중 하나만 반환하시오.

 

 

풀이

정수간의 인접관계를 해시 테이블을 이용하여 그래프로 만든다.

인접한 정수가 단 하나인 노드를 하나 찾아서 그 노드를 기준으로 DFS하면서, 방문한 숫자마다 배열에 추가하면 된다.

 

코드

C++

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        const int n = adjacentPairs.size()+1;

        unordered_map<int, vector<int>> graph;
        unordered_map<int, bool> restored;

        for(const auto &adjacentPair : adjacentPairs) {
            int a = adjacentPair[0];
            int b = adjacentPair[1];

            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        int start = 0;
        for(const auto &num : graph) {
            if(num.second.size() == 1) {
                start = num.first;
                break;
            }
        }

        queue<int> q;
        q.push(start);
        restored[start] = true;

        vector<int> arr;
        while(!q.empty()) {
            const int curr = q.front();
            q.pop();
            arr.push_back(curr);

            auto next_nums = graph[curr];

            for(const auto &next : next_nums) {
                if(!restored[next]) {
                    q.push(next);
                    restored[next] = true;
                }
            }
        }

        return arr;
    }
};