[LeetCode] 1436. Destination City

https://leetcode.com/problems/destination-city/description/

Destination City - LeetCode

leetcode - Destination City

문제 유형 : 탐색 / dfs

문제 난이도 : Easy

 

문제

You are given the array paths, where paths[i] = [cityA[i], cityB[i]] means there exists a direct path going from cityA[i] to cityB[i]. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

 

당신은 paths라는 배열을 받습니다. paths[i]는 [cityA, cityB]의 형태로 값이 있습니다.

A에서 B로 가는 길이 있다는 의미입니다. 이 길들의 최종 목적지를 반환하시오. 반드시 유효한 답이 나오도록 정해져있습니다.

 

풀이

paths[0]의 목적지를 처음 목적지로 삼습니다.

그리고 순회하면서 paths[i]의 출발점이 목적지와 같으면, 목적지를 갱신하고, 처음부터 다시 순회합니다.

순회를 마치고, 목적지의 변경이 없다면, 그 목적지가 최종 목적지이므로 반환합니다.

 

코드

C++

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        const int n = paths.size();
        
        string destination = paths[0][1];

        while(true) {
            bool flag = false;
            for(int i = 0; i < n; i++) {
                if(paths[i][0] == destination) {
                    destination = paths[i][1];
                    flag = true;
                    break;
                }
            }

            if(!flag) {
                return destination;
            }
        }
        return "";
    }
};