문제 링크
난이도 : Lv. 3
문제 내용
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터
n-1인 정수로 표현합니다. - i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.
입출력 예
| n | computers | return |
|---|---|---|
| 3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
| 3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.
예제 #2
아래와 같이 1개의 네트워크가 있습니다.
문제 분석
DFS를 몇 번 돌려야 하는가? 가 정답인듯.
작성한 코드
#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
vector<bool> visited;
stack<int> nextNodes;
void dfs(vector<vector<int>> &maps, int node)
{
if(visited[node]) return;
visited[node] = true;
for(int i = 0; i < maps[node].size(); i++)
{
if(maps[node][i] == 1 && !visited[i] && i != node)
{
nextNodes.push(i);
}
}
if(nextNodes.empty()) return;
int nextNode = nextNodes.top();
nextNodes.pop();
dfs(maps, nextNode);
}
int solution(int n, vector<vector<int>> computers) {
visited.assign(n, false);
int answer = 0;
bool isDone = false;
while(!isDone)
{
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
answer++;
dfs(computers, i);
break;
}
else if (i == n-1) isDone = true;
}
}
return answer;
}- 테스트 케이스는 통과했는데, 실제 채점에서 약 7개 정도 틀림.. 왜인지 모르겠음
Chatgpt의 분석
✔ 네가 빼먹은 핵심 포인트 1
DFS 흐름을 “스택 하나”로만 이어가고 있음 → 한 네트워크의 모든 노드를 끝까지 방문하지 못함
너는 다음 노드를 스택에서 딱 하나만 pop 해서 DFS를 이어가고 있어.
문제는 그 하나를 방문한 뒤, 그 노드에서 또 발견된 인접 노드들은 다시 push만 하고, 바로 다음으로 가지 않음.
즉,
-
인접한 노드는 push
-
“스택이 비면 끝”
-
스택에서 하나만 뽑아서 재귀
-
다시 그 재귀 안에서도 하나만 뽑아서 재귀
이 흐름 때문에 한 레벨씩만 내려가고, 다른 자식 노드들은 나중에 처리되지 않음.
→ 결국 한 네트워크 안의 노드를 모두 방문하지 못해 컴포넌트 개수가 늘어남.
✔ 네가 빼먹은 핵심 포인트 2
스택을 지역적으로 사용하지 않고 전역으로 둠 → 이전 네트워크의 잔여 노드가 다음 DFS에 섞임
전역 nextNodes에 계속 push만 하고, 네트워크 하나 끝났을 때 스택을 비우는 로직이 없음.
그래서
-
첫 DFS에서 넣어둔 node들이 남아 있고
-
다음 네트워크 탐색 시 그 leftover가 섞임
-
방문해야 하는 범위가 꼬이거나 잘못된 컴포넌트 수 계산으로 이어짐.
✔ 네가 착각한 포인트
“스택 DFS”라고 해서 stack + recursion을 혼용하면 안 됨
재귀 DFS는 call stack만으로 충분하고,
stack DFS는 while(stack) 구조로 이루어져야 함.
지금처럼 “전역 스택에 push → 재귀한 번 → push → 재귀한 번” 구조는 DFS의 핵심인 모든 인접 노드 순차 방문이 누락됨.
✔ 요약
너의 코드는 결국 두 가지를 놓쳤음.
-
스택에 넣은 모든 노드를 DFS로 방문하는 루프가 없음
-
스택을 한 DFS(= 한 네트워크)마다 초기화하지 않음
이 두 가지 때문에 네트워크를 온전히 탐색하지 못하는 게 핵심 오류임.
그래서 바꾼 코드
#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
vector<bool> visited;
stack<int> nextNodes;
void dfs(vector<vector<int>> &maps, int node)
{
if(visited[node]) return;
visited[node] = true;
for(int i = 0; i < maps[node].size(); i++)
{
if(maps[node][i] == 1 && !visited[i] && i != node)
{
nextNodes.push(i);
}
}
while(!nextNodes.empty())
{
int nextNode = nextNodes.top();
nextNodes.pop();
dfs(maps, nextNode);
}
}
int solution(int n, vector<vector<int>> computers) {
visited.assign(n, false);
int answer = 0;
bool isDone = false;
while(!isDone)
{
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
answer++;
while(!nextNodes.empty()) nextNodes.pop();
dfs(computers, i);
break;
}
else if (i == n-1) isDone = true;
}
}
return answer;
}우수 코드 분석
#include<string>
#include<vector>
using namespace std;
vector<bool> visited;
void dfs(const vector<vector<int>> &network, int node)
{
visited[node] = true;
for (int i = 0; i < network[node].size(); i++)
{
if(network[node][i] && !visited[i])
dfs(network, i);
}
}
int solution(int n, vector<vector<int>> computers)
{
visited = vector<bool>(computers.size(), false);
int networkCount = 0;
for(int i = 0 ; i < computers.size(); i++)
{
if(!visited[i])
{
dfs(computers, i);
networkCount++;
}
}
}