네트워크 43162

문제

접근 방법

이해가 안 된다면 입출력 예를 보면 된다.

[[1, 1, 0], [1, 1, 0], [0, 0, 1]]

0번 인덱스 1번 인덱스가 이어졌고 2번은 아니란 뜻이다. 즉 2개의 영역이다.

[[1, 1, 0], [1, 1, 1], [0, 1, 1]]

0번 1번이 이어졌고
1번은 0번, 2번이 이어졌으면
2번은 1번과 이어졌다는 뜻이다.
즉 0, 1, 2가 간접적으로 이어졌기에 1개의 영역이란 뜻이다.

코드

#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> computers)
{
    int answer = 0;
    vector<bool> visted(n);
    queue<int> bfs;
    for (int i = 0; i < n; ++i)
    {
        if (visted[i]) // 이미 방문한 경우
            continue;
        ++answer;
        visted[i] = true;
        bfs.push(i);
        while (!bfs.empty())
        {
            int cur = bfs.front();
            bfs.pop();
            for (int j = 0; j < n; ++j)
            {
                if (cur == j || !computers[cur][j] || visted[j]) // 나 자신인 경우, 길이 없는 경우 ,이미 방문한 경우
                    continue;
                visted[j] = true;
                bfs.push(j);
            }
        }
    }
    return answer;
}

풀이

양방향이기에 방문했는지에 대한 1차원 배열만 있으면 된다.
연결된 다른 컴퓨터로 이동해 아직 안 가본 컴퓨터를 계속 방문한다고 생각하면 된다.