20220807_TIL_알고리즘 리뷰

codeing999·2022년 8월 7일

TIL/WIL

목록 보기

13/22

오늘은 DFS 문제를 하나 풀었는데
얼마전에 DFS/BFS에 관해 조사해보기도 했고해서
관련 리뷰를 써보려고 한다.

DFS와 BFS

DFS와 BFS 발표 자료
이론적인 것은 여기에 적어두었다.

문제풀이

깃헙 링크 : https://github.com/unchaptered/algorithm/tree/main/advanced

DFS

DFS란?

그래프 탐색 알고리즘에는 너비우선탐색(BFS), 깊이우선탐색(DFS) 알고리즘이 있다.
그래프 탐색이란 여러 개의 점(노드)들과 그 것들을 연결하는 선(엣지)들이 주어졌을 때 전체 노드를 탐색하는 것이라 할 수 있겠다.
연결된 점들을 찾거나, 특정 시작점과 도착점의 최단거리 등을 찾는 문제에 쓰이는 알고리즘이다.
그중에서도 DFS는 깊이우선이란 이름대로, 하나의 연결된 점을 정해서 가장 깊이까지 우선 탐색하고
그 다음 점을 다시 정해서 또 다시 깊이까지 탐색해보는 방법이다.

분석 : 네트워크

프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

풀이 : 네트워크

접근 : 연결되어있는 덩어리들의 개수를 구하는 문제이므로 최근접노드들을 우선 쫒아가는 BFS는 연결된 집단을
추적하기에 적합하지 않아보였다.
그래서 한 경로를 끝까지 파고들어가는 DFS가 더 적절하다는 판단을 해서 DFS로 풀기로하였다.
또한, DFS는 재귀함수나 스택으로 구현하고 그중에서도 주로 재귀함수로 구현한다고 알고있어서
재귀함수로 구현해야겠다고 판단하였다.

구체적으로는, 일단 시작점 노드에서부터 연결된 모든 노드들을 탐색하는데, 연결된 한노드를 발견한 순간
그 노드를 시작점으로 하여 다시 재귀적으로 호출하는 방식이다.
다만 이때, 이번 네트워크의 처음 시작점(루트노드)를 기억해두었다가, 그 루트노드에서 호출한 재귀함수들이 다 끝나고
돌아왔을 때에만이 그것과 연결된 모든 노드들을 찾은 시점이기 때문에.
함수를 실행할 때 지금 탐색하는 이 노드가 루트노드인지 아닌지 구분하는 것이 필요할 것으로 판단했다.
이렇게 함으로써 한 루트노드를 기준으로 하는 모든 연결점을 찾고나면.
이제 이 네트워크와 연결이 안되어있는 다른 노드 중 가장 작은 인덱스 노드를 새로운 루트노드로하여
또 탐색을 시작한다.
문제점 : 여러 테스트 케이스를 추가해보면 다 해결이 되었었는데 제출을 하면 많은 문제들을 틀리고있다.
반례를 찾았는데 1번과 2번은 연결이 안되어있는데 1번과 3번이 연결되어있고 3번과 2번이 연결되어있는 경우와 같은 상황일 때 틀리고 있다.
현재 자기보다 큰 인덱스 노드와만 탐색을 하기 때문에 3번이 2번과 연결되는 걸 잡아내지 못하고 있다.
이러해서, 탐색을 항상 1번 노드를 대상으로부터 하게 바꿔보았지만 너무 루프가 많이 돌아서 실패하고 있다.
조금만 더 하면 해결 될 것 같지만 아직 방법을 생각하지 못했다.

//https://school.programmers.co.kr/learn/courses/30/lessons/43162#
var count = 0;
var doneroot = [];
var donenode = [];

//i 현재 노드
//root 현재 탐색이 시작된 노드
function DFS(i, n, computers, root) {

    if (i === root) doneroot.push(root);
    for (let j = i + 1; j < n; j++) {
        //console.log("A:", i, j, root, doneroot);
        if (computers[i][j] === 1)
            DFS(j, n, computers, root);
    }
    if (donenode.includes(i) === false) donenode.push(i);
    if (i === root) {
        for (let j = i + 1; j < n; j++) {
            //console.log("B:", j,  root, doneroot, donenode);
            if (donenode.includes(j) === false) {

                DFS(j, n, computers, j);
            }
        }
    }


    return doneroot.length;

}

function solution(n, computers) {

    return DFS(0, n, computers, 0);
}

해결 : 아래 코드로 해결하였다. 위에 쓴대로 for문의 시작을 1로하면
RangeError: Maximum call stack size exceeded
이와 같이 재귀함수의 최대콜 스택이 초과됐다고 뜨는데
방문한 노드를 저장해두던
if (donenode.includes(i) === false )donenode.push(i);
이 코드를 윗줄로 옮기니까 해결되었다.

var count = 0;
var doneroot = [];
var donenode = [];

//i 현재 노드
//root 현재 탐색이 시작된 노드
function DFS(i, n, computers, root) {
    if (i === root ) doneroot.push(root);
    if (donenode.includes(i) === false )donenode.push(i);
    for (let j = 1; j< n; j++){
        //console.log("A:", i, j, root, donenode, doneroot);
        if ((donenode.includes(j) === false ) && (computers[i][j] === 1) )
            DFS(j, n, computers, root);
    }
    
    if ( i === root){
        for (let j = i+1; j< n; j++){
        //console.log("B:", j,  root, doneroot, donenode);
        if (donenode.includes(j) === false ) {
            
            DFS(j, n, computers, j);
        }
    }
    }
    
    return doneroot.length;
    
}

function solution(n, computers) {
    
    return DFS(0, n, computers, 0);
  
}