프로그래머스 : 동굴탐험 JavaScript

class Queue {
    constructor() {
        this._arr = [];
    }
    
    push(value) {
        this._arr.push(value);
    }
    
    pop() {
        return this._arr.shift();
    }

    isEmpty() {
        return this._arr.length === 0;
    }
}

var Edge;
var beforePath;
var visit;
function solution(n, path, order) {
    Edge = Array.from({length: n},() => []);
    beforePath = Array(n);
    visit = Array(n).fill(false);
    
    for(let o of order) {
        beforePath[o[1]] = o[0];
    }

    if(beforePath[0] !== undefined) {
        return false;
    }
    
    for(let p of path) {
        Edge[p[0]].push(p[1]);
        Edge[p[1]].push(p[0]);
    }
    const q = new Queue();
    const un_entered = new Array(n).fill(-1);
    visit[0] =true;
    q.push(0);
    var answer = false;
    var cnt = 1;

    while(!q.isEmpty()) {
        let cur = q.pop();

        for(let next of Edge[cur]) {
            if (beforePath[next] !== undefined && !visit[beforePath[next]]) {
                un_entered[beforePath[next]] = next;
                continue;
            }

            if(visit[next])
                continue;

            if(un_entered[next] != -1) {
                cnt++;
                visit[un_entered[next]] = true;
                q.push(un_entered[next]);
            }
            
            visit[next] = true;
            cnt++;
            q.push(next);
        }
    }

    if(cnt === n )
        answer = true;

    return answer;
}

 

BFS 탐색을 돌면서 다음으로 이동할 node에 상황에 따라서 push하거나 잠시 다른 buffer에 저장한다.

 

1. 다음 노드는 방문은 하지않았지만 이전에 방문해야할 노드가 있어야하는 경우 un_entered 배열에 저장하고 continue;

 

2. 다음 노드가 방문했을 경우 sikip

 

3. 다음 노드가 방문하지 않았을 경우 cnt++; visit체크하고 push

 - 이 노드로 인해서 un_entered해금이 풀리는 경우 cnt++ visit 체크하고 push

 

JavaScript는 큐가없다. 따라서 shift는 상당히 느린 연산이다. 따라서 이문제를 현재노드를 방문하고 visit을 처리하는 경우는 중복되는 노드가 있기 때문에 상당히 위험하다. 따라서 현재 노드에서 다음 노드로 갈때 visit을 처리해주는게 중요하다.

 

이문제는 특이 케이스가 존재하는데(이것은 다른 블로그님 참조)

 

바로 0을 방문하기위해서 어떤 노드를 거처야한다는 케이스에 대한 제약사항이 없다.. 이부분이 어려운게 초기 0번째노드는 무조건 푸시가 되기 때문에 이케이스에 대해서는 에러가남 따라서 anyNumber -> 0 존재하면 무조건 0이 push를 못하니 fasle를 반환.