강의로 돌아가기
전용민

주어지는 그래프는 양방향 그래프가 아닐 수도 있나요?...

제목 그대로의 질문입니다. 주어진 그래프가 양방향 그래프가 아닐 수 있나요??..

작성중인 코드―solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function solution(n, computers) {
    let answer = 0;
    // 1. 각 node를 나타내는 map 혹은 배열 선언(방문 완료)
    let queue = new Array(n).fill(false);

    queue[0] = true;
    answer++;
    bfs(0, computers, queue);
    // 0번 노드에서 연결된 노드 찾기

    while (queue.includes(false)) {
        for (let i = 1; i < computers.length; i++) {
            if (queue[i] === false) {
                queue[i] = true;
                answer++;
                bfs(i, computers, queue);
            }
        }
    }

    return answer;
}

function bfs(i, computers, queue) {
    if (queue.includes(false) === false) {
        return;
    }
    for (let j = i + 1; j < computers[i].length; j++) {
        if (computers[i][j] === 1) {
            queue[j] = true;
            bfs(j, computers, queue);
        }
    }
}
1 개의 답변
JieunKim

예제 설명의 그림을 통해, 이 문제는 방향성이 없는 그래프(또는 양방향 그래프)만 입력으로 주어지는 걸 알 수 있습니다.

또한 만약 방향성이 있는 그래프라면 dfs, bfs만으로 답을 찾을 수 없습니다.
예를 들어, B->A->C 같은 그래프에서 연결된 그래프 수는 1개지만, dfs나 bfs를 A에서 시작하면 결과는 2가 되어 틀립니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.