백준 : 2606번, 바이러스

문제 주소 : www.acmicpc.net/problem/2606

정답 비율 : 44.625% (2021.02.28 14:09 기준)

2606번: 바이러스

 

문제 요약 :

무향 그래프가 주어지고 1번 노드를 선택합니다. 해당 노드가 속해있는 컴포넌트에 있는 자신의 제외한 노드의 개수를 구하는 문제입니다.

 

문제 조건 :

입력 : 첫 줄에는 노드의 개수(N)가 주어집니다. (N : 1 ~ 100) 두 번째 줄에는 간선의 개수(E)가 주어집니다. 그 후로 E 만큼 연결된 노드 쌍이 주어집니다.

출력 : 1번 노드가 속해있는 컴포넌트에 있는 노드의 개수(자신 제외)

시간 : 1초

 

문제 풀이 :

간단한 그래프 탐색 문제입니다. BFS로 문제를 해결하였습니다.

 

C99

#include<stdio.h>

int graph[100][100];
int queue[100];
int visit[100];

int main()
{
	int Node, Edge, i = -1;
	int front = 0, rear = 0, ans = 0;
	
	scanf("%d %d", &Node, &Edge);
	
	for(i = 0; i < Edge; i++)
	{
		int n1, n2;
		scanf("%d %d", &n1, &n2);
		
		graph[n1 - 1][n2 - 1] = 1;
		graph[n2 - 1][n1 - 1] = 1;
	}
	
	visit[0] = 1;
	queue[rear++] = 0;
	
	while(front != rear)
	{
		for(i = 0; i < Node; i++)
		{
			if(graph[queue[front]][i] == 1 && visit[i] != 1)
			{
				ans++;
				visit[i] = 1;
				queue[rear++] = i;
			}
		}
		front++;
	}
	
	printf("%d", ans);
}

 

Python3

#solve 2606

Max_Node = int(input())
Max_Edge = int(input())

Visit = [0 for i in range(Max_Node + 1)]
Graph = {i : [] for i in range(1, Max_Node + 1)}
Queue = []

for i in range(Max_Edge) :
    a, b = list(map(int, input().split()))
    Graph[a] += [b]
    Graph[b] += [a]

Visit[1] = 1
Queue.append(1)

while Queue :
    Node = Queue.pop(0)

    for i in Graph[Node] :
        if Visit[i] == 0 and i != 0 :
            Queue.append(i)
            Visit[i] = 1

print(sum(Visit) - 1)