[프로그래머스][백트래킹] 바이러스 파이프 구현

     

목차

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/468373

프로그래머스

 

 

문제 구현 방향

배열을 어디까지 복구할 것인지가 핵심

새로 감염된 것들과 기존의 감염된 것들을 어떻게 분리할 것인지?

 

1. 새로 감염된 것들을 방문하고 새로운 배열에 저장한다.

2. 새로 감염된 것 + 기존 감염된 것을 통해 dfs를 진행한다. (dfs는 type에 따라 진행)

3. 새로 감염된 것들의 방문을 원상 복구 해준다.

 

 

코드 구현

function solution(n, infection, edges, k) {
    var answer = 0;
    let adjList = Array.from({length: n+1}, ()=> []);
    let visit = Array(n+1).fill(0);
    edges.forEach((edge)=>{
        let [from, to, type] = edge;
        adjList[from].push([to, type]);
        adjList[to].push([from, type]);
    })

    function infect(nodes, pipeType){
        let queue = [];
        let infected = [];
        nodes.forEach((node)=>{
            queue.push(node);});
        
        while(queue.length){
            let cur = queue.shift();
            for(let next of adjList[cur]){
                let [nNode, nType] = next;
                if(nType === pipeType && !visit[nNode]){
                    infected.push(nNode);
                    queue.push(nNode);
                    visit[nNode] = 1;
                }
            }
        }
        return infected;
    }

    function dfs(nodes, step){
        //새로 방문을 했다.
        nodes.forEach((node)=>visit[node] = 1);
        answer = Math.max(visit.reduce((acc, cur)=> acc +=cur, 0), answer);
        
        //이때 파이프 개수넘으면 그만 간다.
        if(step === k) return;
        for(let type = 1; type<=3; type++){
            //새로 감염이 되었다.
            let newInfect = infect(nodes, type);
            if(newInfect.length === 0)continue;
            dfs([...nodes, ...newInfect], step+1);
            //새로 감염된 것을 복구한다.
            newInfect.forEach((nI)=> visit[nI] = 0);
        }
    }
    
    dfs([infection], 0);
    
    return answer;
}

//파이프가 열리면 감염
//어디까지 전달해줄 것인가가 핵심
//방문처리를 어디까지 할 것인가가 핵심
//현재 노드는 방문한 상태 유지  복귀할 노드들 => 새로 감염된 노드들