DFS

이번주 스터디 주제는 DFS와 BFS이다.

첫번째로 풀어야하는 문제는 '백준 2606 바이러스' 이다.

DFS에 대한 인강을 찾아봤는데 Deep 의 약자로 일반적으로 재귀함수로 구현되면 재귀를 타고, 타고, 타서 탈출조건에 도달하고 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식이라는 것까지만 알고 일단 문제를 풀어보기로 했다.

https://www.acmicpc.net/problem/2606

단순히 개념만 가지고 알고리즘을 푸려고 하니 어려워서 일단 다른 사람들이 만든 코드를 보고 공부하려고 했다. 그런데 다른 사람이 짠 코드 이해가 잘 가지 않는다. 그래서 DFS에 대한 개념공부를 하기로 했다.

공부는 예전에 인프런에서 구매해두었던 '자바스크립트 알고리즘 문제풀이(코딩테스트 대비)'를 활용하도록 하겠다.

INDEX

• 재귀함수와 스택프레임
• 이진수 출력
• 이진트리 순회
• 부분집합 구하기
• 합이 같은 부분집합
• 바둑이 승차
• 최대점수 구하기
•  

---

1. 재귀함수와 스택프레임 - 스택개념알기

재귀함수
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.

* 입력예제
3
* 출력예제
1 2 3

function solution(n) {
	function DFS(L) {
    	if (L === 0) return; // 재귀함수는 무한루프를 돌 수 있기 때문에 꼭 종단점을 지정해주어야한다.
        else {
        	console.log(L);
        	DFS(L-1); // DFS함수 내부에서 다시 DFS를 호출했기 때문에 재귀함수이다.
        }
    }
    DFS(n)
}
solution(3); // 3 2 1

여기까지는 이해가 간다. 그런데 만약 'console.log(L)'과 'DFS(L-1)'의 행을 바꾸면 어떻게 될까. 콘솔창에는 1 2 3이 찍히게 된다. 왜 그럴까. 바로 스택을 쌓기 때문이다.

DFS 알고리즘을 구현하기 위해서는 스택의 특징을 잘 활용하는 것이 중요하다.

 

2. 이진수 출력(재귀) - 스택복습

재귀함수를 이용한 이진수 출력
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로개름을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.

* 입력예제
11
* 출력예제
1011

function solution(n) {
	let answer = '';
    DFS(n);
    // m은 몫이 된다.
    function DFS(m) {
    	if (m === 0) return
        else {
            DFS(parseInt(m / 2))
        	answer += m % 2
        }
    }
	return answer;
}

 

3. 이진트리순회(DFS: 깊이우선탐색)

1을 root node(부모)라고 부르고 각 노드 사이의 연결을 단선 또는 엣지라고 부른다.

1(root node)를 기준으로 왼쪽(2)는 n*2가 되고 오른쪽(3)은 n*2+1가 된다.

 

전위순회는 '부모 - 왼쪽 - 오른쪽'을 말한다. 1(부모) - 2(왼쪽) - 4(왼쪽) - 5(오른쪽) - 3(오른쪽) - 6(왼쪽) - 7(오른쪽)이 된다.

중위순회는 '왼쪽 - 부모 - 오른쪽'을 말한다. 4(왼쪽) - 2(부모) - 5(오른쪽) - 1(부모) - 6(왼쪽) - 3(부모) - 7(오른쪽)이 된다.

후위순회는 '왼쪽 - 오른쪽 - 부모'를 말한다. 4(왼쪽) - 5(오른쪽) - 2(부모) - 6(왼쪽) - 7(오른쪽) - 3(부모) - 1(부모)가 된다.

 

위의 전위순회, 중위순회, 후위순회를 코드를 짜보겠다.

// 전위순회
function solution(n) {
    let answer = "";
    function DFS(m) {
    	if (m > 7) return;
        else {
            answer+=m;
            DFS(m*2)
            DFS(m*2+1)
        }
    }
    DFS(n);
    return answer;
}
console.log(solution(1));

// 중위순회
function solution(n) {
    let answer = "";
    function DFS(m) {
    	if (m > 7) return;
        else {
            DFS(m*2)
            answer+=m;
            DFS(m*2+1)
        }
    }
    DFS(n);
    return answer;
}
console.log(solution(1));

// 후위순회
function solution(n) {
    let answer = "";
    function DFS(m) {
    	if (m > 7) return;
        else {
            DFS(m*2);
            DFS(m*2+1);
			answer+=m;
        }
    }
    DFS(n);
    return answer;
}
console.log(solution(1));

 

4. 부분집합 구하기(이진트리 DFS)

부분집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 단 공집합은 출력하지 않습니다. (아~ {} 이렇게 될 경우는 빼라는 거)

* 입력예제
3
* 출력예제
1 2 3
1 2
1 3
1
2 3
2
3

쉬운 방법으로는 2의 3제곱 - 1을 해주면 된다.

 

1이 참여한다 or 참여하지 않는다는 ch배열을 만들어 기록해야한다.

function solution(n) {
    let answer = [];
    let ch = Array.from({length: n+1}, () => 0);
    function DFS(v) {
    	if (v===n+1) {
        	let tmp = ""
        	for(let i = 1; i <= n; i++) {
            	if(ch[i] === 1) tmp+=i+" ";
            }
            if(tmp.length > 0) answer.push(tmp.trim());
        } else {
            ch[v] = 1;
            DFS(v+1);
            ch[v] = 0;
            DFS(v+1);
        }
    }
    DFS(1)
    return answer;
}

console.log(solution(3))

5. 합이 같은 부분집합

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주 어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.


* 입력예제
6
1 3 5 6 7 10
* 출력예제
YES

function solution(arr) {
    let answer = "NO";
    let ch = Array.from({ length: arr.length }, () => 0);
    const total = arr.reduce((sum, curr) => sum+curr, 0);
    DFS(0);
    function DFS(v) {
        if(v === arr.length) {
            let sum = 0;
            for(let i = 0; i < ch.length; i++) {
                if (ch[i] === 1) sum+=arr[i]
            }
            if (sum*2 === total) answer = "YES"
        } else {
            ch[v] = 1;
            DFS(v+1);
            ch[v] = 0;
            DFS(v+1);
        }
    }
    return answer
}

나는 위의 4. 부분집합 구하기와 같은 방식으로 5. 합이 같은 부분집합을 풀었다. 강의에서는 다른 방식으로 구현했으므로 소개하겠다.

function solution(arr) {
    let answer = "NO", flag = 0; // 이미 "YES"인데 계속 식별할 필요가 없으므로
    const total = arr.reduce((sum, curr) => sum+curr, 0);
    
    function DFS(L, sum) {
    	if (flag) return // answer이 "YES"가 되면 빠져나온다.
    	if (L === arr.length) {
        	if ((total-sum)===sum) {
            	answer = "YES";
                flag = 1
            }
        } else {
            DFS(L+1, sum);
            DFS(L+1, sum+arr[L])
        }
    }
    DFS(0, 0)
    return answer;
}
console.log(solution([1, 3, 5, 6, 7, 10]))

 

6. 바둑이 승차(DFS)

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

* 입력예제
259 5
81
58
42
33
61
* 출력예제
242

function solution (arr) {
    let max = 0;
    function DFS(L, sum) {
        if (L === arr.length) {
            if (sum<=259) {
                if (max < sum) max = sum;
            }
        } else {
            DFS(L+1, sum+arr[L]);
            DFS(L+1, sum);
        }
    }
    DFS(0, 0);
    return max;
}
console.log(solution([81, 58, 42, 33, 61]))

 

7. 최대점수 구하기

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
* 입력예제
5 20
10 5
25 12
15 8
6 3
7 4
* 출력예제
41

function solution(arr) {
    let max = 0;
    function DFS(L, sumQ, sumT) {
        if (L === arr.length) {
            if (sumT <= 20) {
                if (max < sumQ) max = sumQ
            }
        } else {
            DFS(L+1, sumQ+arr[L][0], sumT+arr[L][1]);
            DFS(L+1, sumQ, sumT);
        }
    }
    DFS(0, 0, 0)
    return max
}
console.log(solution([[10, 5], [25, 12], [15,8], [6,3], [7, 4]]))

이제 어느정도 DFS에 대해 알게된 거 같아서 다시 바이러스 문제를 풀어보려고 하니 이건 그래프 정렬이었다. 그래서 다음 포스팅에서는 그래프 정렬에 대해서 알아보겠다.

 

 

참고:

• https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard
• https://youtu.be/BsYbdUnKZ-Y

 

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의