오늘은 DFS 문제를 하나 풀었는데
얼마전에 DFS/BFS에 관해 조사해보기도 했고해서
관련 리뷰를 써보려고 한다.
DFS와 BFS 발표 자료
이론적인 것은 여기에 적어두었다.
깃헙 링크 : https://github.com/unchaptered/algorithm/tree/main/advanced
그래프 탐색 알고리즘에는 너비우선탐색(BFS), 깊이우선탐색(DFS) 알고리즘이 있다.
그래프 탐색이란 여러 개의 점(노드)들과 그 것들을 연결하는 선(엣지)들이 주어졌을 때 전체 노드를 탐색하는 것이라 할 수 있겠다.
연결된 점들을 찾거나, 특정 시작점과 도착점의 최단거리 등을 찾는 문제에 쓰이는 알고리즘이다.
그중에서도 DFS는 깊이우선이란 이름대로, 하나의 연결된 점을 정해서 가장 깊이까지 우선 탐색하고
그 다음 점을 다시 정해서 또 다시 깊이까지 탐색해보는 방법이다.
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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);
}
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);
}
리커시브를 하나 완성해보고 나니까 느껴진점
이런 식으로 느낌을 잡고 들어가면 앞으로 덜 헷갈릴 것 같다.