프로그래머스 네트워크 dfs/bfs 문제풀이

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

function solution(n, computers){
    let answer = 0;
    let visited = [];
    for (let i = 0; i<n;i++){
        visited.push(false);
    }
    function dfs(graph, now, visited){
        //visited [now] process
        visited[now] = true;
        graph[now].forEach((element, index)=>{
            if(index!==now&&graph[now][index]===1&&visited[index]===false){
                //[connected index] visited process
                dfs(graph, index, visited);
            }
        })
    }
    //dfs run with visited false state
    visited.forEach((element, index) =>{
        if(element === false){
            answer ++;
            dfs(computers, index, visited);
        }
    })
    return answer
}

 

dfs 풀이

 

function solution(n, computers){
    let answer = 0;
    let queue = [];

    let visited = [];
    for(let i=0;i<n; i++){
        visited.push(false);
    }
    visited.forEach((element, index)=>{
        if(element ===false){
            queue.push(index);
            visited[index]=true;
            answer ++;
            while(queue.length){
                //while end statement
                let now = queue.shift();
                computers[now].forEach((element, index)=>{
                    //statement statement 1. visited false, 2. connected -> computers index = 1
                    if(index!==now&&computers[now][index]===1&visited[index]===false){
                        visited[index]= true;
                        queue.push(index);
                    }
                })
            }
        }
    })
    return answer;
}

bfs 풀이

 

문제 풀이 플로우는 다음과 같다.
let answer = 0; 

1. visited를 기준으로 방문 안한곳이 있나를 index로 체크로 해야하기에, visited =[false,...false]를 만든다
2. dfs는 재귀함수로 진행을 하기에 function을 준비하고, bfs는 queue로 진행하기에 queue =[]를 만든다
3. 이제부터 bfs와 dfs풀이가 달라진다
  dfs는 function을 만든다. function(graph, now, visited)
  visited[now] = true //방문처리
  graph[now].forEach((element,index)=>{}
  본인이 본인이아니고(now !==index), 방문 index가 false이며, 현재 그래프와 연결된 것을 찾는다
  있다고하면 재귀함수 dfs(graph, index, visited)를 실행
  
  bfs는 visited.forEach((element, index)=>{})로 각 성분마다, 방문이 안되어있다면(element ===false),
  queue에 index를 넣고, visited[index]를 true로 바꾼뒤에, answer ++를 더한다.
  지금부터 연결된 것들을 찾기 위한 while statement를 실행한다.
  while의 조건은 queue.length의 expression이 0이 될 때까지이다.
  queue를 shift 시키고, shift값을 now로 둔 다음에, computers[now].forEach를 시작한다
  dfs와 같게 본인이 본인이 아니고(now!==index_, 방문 index false, 현재 그래프와 연결된 곳에서
  queue.push(index), visited[index]=true 를 시킨다. 연결된 부분이 없어지면 while문을 나가서 answer을 ++한다
4. return answer

플로우는 재방문을 할필요가 없기때문에, visited false일 때 첫 방문을 하여 connected 된 곳을 찾는 플로우로 진행을 하면 된다. 단지 dfs와 bfs의 차이는, queue를 쓰는가 recursive를 사용하냐에 따라 다르다