Graph

---

: 그래프는 노드(node or vertaxl,정점)와 간선(edge)로 구성된 비선형 자료구조이다. 노드들을 도시라고 가정했을 때 간선은 도시들을 연결해주는 도로인 셈이다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할수 있다.

인접 행렬(Adjacent Matrix)

: 2차원 배열로 그래프의 연결 관계를 표현한 것. 각 연결된 노드는 1로, 연결되지 않는 노드는 0으로 표현한 행렬.위 그래프를 인접행렬로 표현하면 다음과 같다. (간선은 방향이 없다고 가정)

• 모든 노드 간의 관계를 나타내야 하므로 불필요한 메모리 공간을 차지한다는 단점이 있다. (노드 수의 비해 연결된 간선 수가 적다면 불필요한 메모리 공간을 매우 많이 차지함)
  

인접 리스트(Adjacent List)

: 노드 간에 연결관계를 리스트 형식으로 표현하는 것. 튜플형태로 배열로 구현할 수도 있고, 객체로 구현할 수 있다. 나는 map 객체를 이용 하기도 한다. JavaScript 객체로 그래프를 구현하면 아래와 같다. 노드를 key값으로 연결된 노드 리스트를 배열로 value값으로 지정해 준다.

let adjacentdList = {
  0: [1,4],
  1: [0,2,3,4],
  2: [1,3],
  3: [1,2,4],
  4: [0,1,3]
}

그래프를 이용한 알고리즘: 여행경로

---

문제: 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
(문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43164)

Input 예시: [['ICN', 'SFO'], ['ICN', 'ATL'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL','SFO']]

Ouput 예시: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']

function solution(tickets) {
   
    // create airports array (will be Nodes)
    const airports = [];
    for(let ticket of tickets){
        const origin = ticket[0];
        const destination = ticket[1];
        if(!airports.includes(origin)){
            airports.push(origin)
        }
        if(!airports.includes(destination)){
            airports.push(destination)
        }
    }
    
    const map = new Map();
    
    function addNode(airport){
        map.set(airport, []);
    }
    
    function addEdge(origin, destination){
        map.get(origin).push(destination);
    }
    
    // create the graph using MAP 
    // key:origin airport / value:destination
    airports.forEach(addNode);
    tickets.forEach(ticket => addEdge(...ticket));
    
    for(let airport of airports){
        map.get(airport).sort();
    }
    
    // DFS
    let routes = [];
    function dfs(start){
        routes.push(start);
        if(map.get(start).length === 0){
            return;
        }
        const destination = map.get(start).shift();
        dfs(destination);
    }
    
    dfs('ICN');
    return routes;
       
}

풀이)
우선 작성한 위 코드로는 일부 테스트를 통과하지 못했다 :(
어떤 input일때 실패하는지 알 수 없어 왜 안되는지 모르겠다. 계속 건드려도 해결하지 못해 일단 이 코드라도 정리해둔다.

먼저 mapobject를 이용해 주어진 항공권에서 출발하는 공항을 node(key)로, 도착지를 edge(value)로 하는 graph를 구현했다.

이후 이 그래프에서 DFS(deapth-first search, 깊이 우선 탐색)를 이용해 여행경로를 탐색했다.