[알고리즘/javascript][DFS / BFS] 연결된 정점들

연결된 정점들

문제

방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

입력

인자 1: edges

• 2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열, 정수 요소)
• ex) [[0, 1], [1, 2], [3, 4]]

출력

• Number 타입을 리턴해야 합니다.
• 연결된 정점의 컴포넌트의 수를 숫자로 반환합니다.

주의 사항

• 주어진 간선은 무향입니다.
  • [1, 2] 는 정점 1에서 정점 2로도 갈 수 있으며, 정점 2에서 정점 1로도 갈 수 있습니다.

입출력 예시

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
console.log(result); // 3

해당 정점들은 아래와 같은 모양을 하고 있습니다.

 

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[3, 4],
	[3, 5],
]);
console.log(result); // 2

해당 정점들은 아래와 같은 모양을 하고 있습니다.

코드

1. 인접 리스트 

function connectedVertices(edges) {
// TODO: 여기에 코드를 작성합니다.
// 1. 정점의 최댓값을 찾는다.
// 2. 연결리스트 객체를 만들어주고 정점의 갯수만큼 정점을 프로퍼티 키, []를 프로퍼티 값으로 가지는 프로퍼티를 만든다.
// 3. edges를 순회하며, 쌍방간선을 연결해 준다.
// 4. 방문한 정점을 기록해두기 위해 정점의 총 갯수만큼 1차원 배열을 만든다.
// => 방문한 정점은 true, 방문하지 않은 정점은 false 값을 가지도록 한다.
// 5. 모든 정점을 방문하여 연결된 컴포넌트의 숫자를 카운트 해 리턴한다.
// => bfs 또는 dfs 함수를 통해 맨 처음 정점부터 해당 정점과 연결된 정점을 모두 방문한다.
// => 만약 해당 정점과 연결된 정점을 모두 방문하여 다음 방문할 정점이 없으면 bfs 또는 dfs 함수에서 빠져나와 카운팅해준다(컴포넌트 하나 추가).
	let max = Math.max(...edges.flat());
	let list = {};
	for(let i=0;i<=max;i++){
		list[i] = [];
	}
	for(let i=0;i<edges.length;i++){
		list[edges[i][0]].push(edges[i][1]);
		list[edges[i][1]].push(edges[i][0]);
	}
	let visited = new Array(max+1).fill(false);
  let count = 0;
    
  for (let vertex = 0; vertex <= max; vertex++) {        
    if (visited[vertex]===false) {
      	bfs(list, vertex, visited); // dfs(list, vertex, visited);
      	count++;
      }
    }

    return count;
}
// DFS ver
// function dfs(list,vertex,visited){
// 	visited[vertex] = true;
// 	for(let i=0;i<list[vertex].length;i++){
// 		if(!visited[list[vertex][i]]) dfs(list,list[vertex][i],visited);
// 	}
// }

// BFS ver
function bfs(list,vertex,visited){
	let queue = [vertex];
	visited[vertex] = true;
	while(queue.length > 0){
		let current = queue.shift();
		for(let i=0;i<list[current].length;i++){
			if(!visited[list[current][i]]){
				queue.push(list[current][i]);
				visited[list[current][i]] = true;
			}
		}
	}
}

 

2. 인접 행렬 - BFS

// matrix
function connectedVertices(edges) {
    // 인접 행렬 기준

    // 제일 큰 버텍스 찾기.
    const max = Math.max(...edges.flat());

    // 버텍스 찾았다면? 행렬 만들기
    const matrix = new Array(max + 1).fill(0).map(e => new Array(max + 1).fill(0));

    // 엣지 넣기
    edges.forEach(e => {
        matrix[e[0]][e[1]] = 1;
        matrix[e[1]][e[0]] = 1;
    })

    // 탐색에 가장 중요한 건? 두 번 방문하지 않는다.
    let visited = new Array(matrix.length).fill(false);

    // 카운트
    let count = 0;

    // 버텍스를 하나씩 순회하면서 연결된 정점이 있는지 확인한다!!
    for (let i = 0; i < matrix.length; i++) {
        if (visited[i] === false) {
            bfs(matrix, i, visited);
            count++;
        }
    }

    // 카운트를 반환합니다.
    return count;
}


// bfs solution
function bfs(matrix, v, visited) {
    // 큐에 시작점 넣고
    let Q = [v];
    // 방문했다고 표시
    visited[v] = true;
    // 큐에 모든 게 없어질 때까지 반복한다.

    while (Q.length !== 0) {
        // 큐에서 하나 뺀다.
        let current = Q.pop();
        // 현재 정점 확인한다.
        for (let i = 0; i < matrix[current].length; i++) {
            // 정점 순회하면서?
            if (visited[i] !== true && matrix[current][i] === 1) {
                // 큐에 i를 넣자
                Q.unshift(i);
                // 방문했다고 표현하자
                visited[i] = true;
            }
        }
    }
}

 

인접 행렬 - DFS

// dfs solution
// bfs 함수 대신 dfs를 사용해도 결과는 같다.
function dfs(matrix, vertex, visited) {
    // 해당 버텍스에 방문 표시
    visited[vertex] = true;

    // 해당 버텍스의 모든 간선들을 전부 순회한다.
    for (let i = 0; i < matrix[vertex].length; i++) {

        // 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면
        if (visited[i] !== true && matrix[vertex][i] === 1) {
            // dfs를 호출해(재귀) 방문한다.
            dfs(matrix, i, visited);
        }
        // 모든 방문이 종료되면 다음 버텍스를 확인한다.
        // 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트를 센다. 
    }
}