🎯 Achievement Goals

코플릿 [BFS] 인접 행렬 길찾기

👉 인접 행렬 길찾기

문제

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

출력

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

주의사항

주어진 간선은 무향입니다.

입출력 예시

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

인접행렬길찾기1

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

인접행렬 길찾기2

🤔 나의 생각

나는 가장 먼저 인접 행렬을 만들어서 그래프를 표현하고 싶었다. 인접 행렬을 만들기 위해서는 주어진 이차원 배열의 요소중에 가장 큰 값을 알아야한다. 그래야 가장 큰 노드를 알 수 있기 때문이다.
요소의 최대값을 구했으면 이차원 배열을 인접 행렬 형태로 바꿔준다.
그 후 bfs 함수를 구현했다. 이유는 bfs 함수에 노드를 하나씩 넣어줄껀데, 만약 bfs함수를 빠져나오게 되면 그래프가 끊켰다는 뜻이므로 그때 마다 카운트를 해주었다.
노드마다 방문 표시를 해주고 bfs를 통해 연결되어 있는 그래프의 갯수를 세어주었다.

code

// 이차원 배열 요소중의 최댓값 구하기
function connectedVertices(edges) {
    let max = 0;
    for (let i = 0; i < edges.length; i++) {
        let find = Math.max(...edges[i].filter((el) => typeof el === "number"));
        max < find ? max === find : null;
    }

// 인접 행렬 만들기
    let graph = new Array(max+1).fill(0).map((el) => new Array(max+1).fill(0));

// 인접 행렬 간선 연결
    graph.forEach((el) => {
        let [row, col] = el;
        graph[row][col] = 1;
        graph[col][row] = 1;
    });

// bfs 구현
    const bfs = (idx) => {
        let a = [idx];
        check[idx] = true;

        while (a.length !== 0) {
            let vertex = a.shift();

            for (let i = 0; i < graph[vertex].length; i++) {
                if (check[i] === false && graph[vertex][i]) {
                    check[i] = true;
                    a.push(i);
                }
            }
        }
    }

// 연결된 그래프 찾기 시작
    let count = 0;
    let check = new Array(graph.length).fill(false);

    for (let i = 0; i < max; i++) {
        if (check[i] === false) {
            bfs(i);
            count++;
        }
    }
    return count;
}

🙌 느낀점

평소에 프로그래머스 3단계 문제들을 풀면서 BFS에 대해서 어느정도 공부를 해놔서 이 문제를 겨우겨우 풀 수 있었다.. BFS 구현 코드는 거의 다 비슷해서 이제는 BFS 문제들의 코드들은 다 비슷하게 보인다.

배운대로 잘 풀 수 있어서 정말 좋았다!!

👊 내일의 TIW(today I Will)

Greedy, DFS

← Previous Post Next Post →

BFS(Breadth-First Search) 알고리즘

📅 TIL #41