[Algorithm][프로그래머스] lv3 네트워크 | 오늘 문득 깨닳아버렸다.. 때로는 bfs보다 dfs가 더 좋다는 사실을... ㄴㅇㄱ

 

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

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

 

오늘 이 문제를 풀면서

bfs보다 dfs가 진짜 대박 효율적일 때가 있구나라는 것을 

깨달아 버렸습니다..

 

저는 보통 그래프, 지도나 맵 탐색, 네트워크 이런 문제들은 저는 거의 다 bfs로 먼저 로직을 짜왔습니다.

bfs를 활용해서 거의 백준 dfs/bfs문제 100문제인가 정도 푼거같기도 하구요.

 

 

그래서 이 문제도 간단하게

1. 그래프를 만들자.

2. 그래프를 bfs로 탐색하자.

 

이때 기존에 상 하 좌 우를 이제 응용해서 노드와 붙어있는 노드들을 동시에 탐색해나가자! 라고 생각했습니다.\

JS로 풀었구요,,

const solution = (n, computers) => {
    const network = {}
    for (let y=0; y<n;y++) {
        for (let x=y; x<n;x++) {
            if (y===x) continue;
            if (computers[y][x] == 0) continue 
            network[y] ??= []
            network[y].push(x);
            network[x] ??= []
            network[x].push(y);
        }
        network[y] ??= [y]
    }
    
    const visited = computers.map( _ => false);
    return Object.keys(network).filter (e => {
        if (visited[e]) return false;
        visited[e] = true;
        const queue = [e]
        let queueIdx = 0
        while(queue.length > queueIdx) {
            const cur = queue[queueIdx++]
            for (const next of network[cur]) {
                if (visited[next]) continue;
                visited[next] = true
                queue.push(next)
            }
        }
        return true;
    }).length
}

 

network라는 지도에 노드와 인접한 노드를 양방향으로 묶어주고,

queue를 사용해서 동시 탐색을 해나갔습니다.

상 하 좌 우 느낌으로 인접한 하나의 노드에 붙어있는 여러 노드이 방문되지 않았으면 동시에 큐에 넣어주면서 탐색해나갔습니다.

 

---

근데 갑자기 문득 든 생각이 dfs는 어떨까?..

 

const solution2 = (n,computers) => {
    const visited = computers.map(_=>false);
    const dfs = (i) => {
        visited[i] = true;
        for (let j=0;j<n;j++) {
            if (computers[j][i] === 1 && !visited[j]) dfs[j];
        }
    }
    let count = 0;
    for (let i = 0; i<n;i++) {
        if(!visited[i]) { 
            dfs[i]
            count++;
        }
    }
    return count;
}

 

오늘 느낌이 완전 다르다는 것을 느꼈습니다.

문제에서는 i 노드와 j노드가 인접하다 라는 것은 computer[j][i]이니까.. 이를 활용해서 인접하면 계속 인접한 부분 탐색해나가면서 방문 체크.. 아니면 끝!

 

결국 포문 두 번 쓰지만, 두번이 두번이 아닌.. 그런느낌? 최적화된 그런느낌.. 

그리고 bfs보다 dfs가 재귀 종료조건만 잘 해준다면 오히려 더 쉬운느낌..

 

bfs는 맨날 queue에 넣으면서 상 하 좌 우나 대각선까지 탐색을 해나가야 하는데, dfs는 지금탐색하는 이 경로 탐색하고 "어 아니네?" 종료.. 그러면서도 탐색한 부분들은 더이상 탐색하지 않는 이런 느낌으로 훨씬 직관적이고 간단했습니다...

 

 

여기에 이제 JS만의 그런 느낌을 더해주면

const solution(n, computers) => {
  const visited = computers.map{_=>false);
  const dfs = (i) => visited[i] || (visited[i] = true, computers[i].forEach((node, j)=> node && dfs(j)))
  return computers.map(_=>_).reduce((acc,_,i)=>visited[i] ? acc : (dfs(i), acc+1),0)
}

 

JS에서는

|| 오어(or) 연산자는

A || B라면 A가 falsy라면? B 실행!

 

그래서 visited[i] 방문하지 않았다면 || (...) 오른쪽 구간을 실행하는데 

이때 visited[i]를 방문하면서 , 콤마 연산자를 통해서 C, D C로직을 수행하고 D로직을 이어서 수행하자.. 이런 느낌으로

computers[i] i노드에 인접한 노드 중 j노드가 1인 경우 node && dfs(j)

 

&& 앤드(and) 연산자는 A && B 에서 A가 true면 B를 실행합니다.

그렇게 또 dfs(j)를 수행합니다.