[백준 2606] 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

#include <stdio.h>
int N;
int c;
int computer[100 + 2][100 + 2];
int visited[100 + 2];
int cnt;

void input(void)
{
	scanf("%d %d", &N, &c);
	int v1 = 0, v2 = 0;		// 지역변수 초기화해줄것 // 이거 안해주면 틀림
	for (int i = 0; i < c; i++) {
		scanf("%d %d", &v1, &v2);
		// 인접행렬 방식
		computer[v1][v2] = 1;
		computer[v2][v1] = 1;
	}
}	

void get_virus(int node)
{
	visited[node] = 1;	// 현재 노드 방문처리
	cnt++;

	for (int i = 1; i <= N; i++) {
		if (visited[i] == 1) continue;
		if (computer[node][i] == 0) continue;
		get_virus(i);
		//printf("%d ", i);
	}
}

int main(void)
{
	input();
	get_virus(1);
	printf("%d", cnt - 1);	//1번 컴퓨터 제외
	return 0;
}

아C.... 이거 할말 많다... 

DFS 기초문제라서 십분컷 구현했는데 계속 25%에서 틀렸다. 

2번을 틀리고 한 시간을 디버깅했는데 안나와서 진짜 개 허탈하게 있을때... 눈 앞에 보인... 초기화하지 않은 지역변수..... 

설마 저것때문에 틀리리라고는 상상도 못했는데 0으로 초기화하니까 바로 AC받았다 ㅋㅋㅋㅋㅋㅋㅋ 존트 짜증나.. 

 

 

혹시나 백준에 있는 모든 반례들을 넣어봤는데 정상 출력되지만 AC를 받지 못하신 분은 ... 지역변수를 초기화 하십시오....

 

 

 

(++22.09.04 추가)

해당 문제를 스택으로 풀어보았다. 

깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 아래와 같이 구현 가능하다. 

#include <cstdio>
#include <iostream>
#include <stack>

int N, M;	// 컴퓨터의 수, 쌍의 수
int edge[100 + 10][100 + 10];	// 연결여부 저장
int visited[100 + 10];		// 방문여부 저장

std::stack<int> stk;


void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int u = 0; int v = 0; 
		scanf("%d %d", &u, &v);
		edge[u][v] = 1;
		edge[v][u] = 1;
	}
}


void virus(int node)
{
	visited[node] = 1;
	stk.push(node);
	//printf("%d ", stk.top());

	for (int i = 1; i <= N; i++) {
		if (visited[i] == 1 || edge[i][node] == 0) continue;
		virus(i);
	}
}


int main()
{
	input();
	virus(1);
	printf("%d", stk.size() - 1);	// 1번 노드 제외
	return 0;
}

1번과 인접한 노드들 중 번호가 낮은 노드 부터 방문하며 방문표시하고 스택에 담는다. 

가장 마지막에 스택 사이즈에서 1을 빼는 이유는 1번 컴퓨터가 스택 가장 아래쪽에 포함되어 있기 때문이다. 

만약, "1번 컴퓨터와 연결된 모든 노드들을 차례대로 출력하라"는 요구조건이 있다면, 인접한 노드에 방문할 때 마다 printf("%d\n", stk.top())을 하여 스택의 가장 위쪽에 있는 수를 인쇄해주면 된다.