C++ 프로그래머스 코딩테스트 - 네트워크 (43162)

네트워크

Level 3

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

 

서로 이어진 노드 찾기

 

 

1 - 2 처럼 이어진 네트워크를 하나로 본다.

위 경우 네트워크의 총 개수는 2개이다. 1 - 2  /  3

 

 

나의 풀이

int solution(int n, vector<vector<int>> computers)
{
	// 단방향 네트워크 체크.
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (computers[i][j] != computers[j][i])
			{
				computers[i][j] = 0;
				computers[j][i] = 0;
			}

	vector<vector<int>> visitCheck = computers;
	int cnt = 0;

	for (int i = 0; i < n; ++i)
	{
		// 한번 방문한 노드는 재검색 X
		if (visitCheck[i][i] != 1) continue;

		queue<int> q;
		q.push(i);

		while (!q.empty())
		{
			int computer = q.front();
			q.pop();
			for (int k = 0; k < n; ++k)
			{
				// 자기 자신은 pass
				if (k == computer) continue;
				if (computers[computer][k] == 1 && visitCheck[computer][k] >= 0 && visitCheck[k][computer] >= 0)
				{
					q.push(k);
					visitCheck[computer][k] = -1;
					visitCheck[k][k] = -1;
				}
			}
		}
		++cnt;
	}
	return cnt;
}

 

 

먼저, 단방향 네트워크를 제거해주고

BFS로 노드들을 탐색한다.

 

 

BFS 너비 우선 탐색 (Breadth-First Search)

그림 출처 https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90