SWEA 7465번 - 창용 마을 무리의 개수

문제 바로가기

🙄 문제 이해

단순 그래프 탐색 문제 입니다.

무리가 곧 간선으로 연결된 그래프가 되며, 사람이 노드가 됩니다.

무리의 갯수를 세는 것이므로, 노드와 간선으로 이뤄진 네트워크의 갯수를 세면 됩니다.

📝 문제 풀이

그래프 정보를 입력받고, BFS 탐색을 통해 무리의 갯수를 체크했습니다.
BFS 함수 호출 횟수가 곧 무리의 갯수가 되며, 그래프를 입력은 양방향으로 연결된 그래프로 받습니다.

가중치가 없는 양방향 그래프의 경우 노드 갯수 + 1 의 배열을 생성 후 연결된 노드끼리 append를 수행해주면 됩니다.

이후 BFS 탐색은 일반적은 그래프에서의 BFS 탐색과 동일합니다.
방문처리와 큐를 통해 탐색을 수행합니다.

💻 Python 코드

#SWEA 창용마을 무리의 개수
from collections import deque

def bfs(i,graph, visited):
    q = deque()
    q.append(i)
    visited[i] = True
    while q:
        v = q.popleft()
        for j in graph[v]:
            if graph[j] and visited[j] == False:
                visited[j] = True
                q.append(j)

T = int(input())
for t in range(1,1+T):
    n, m = map(int, input().split()) #n:노드 / m:간선
    graph = [[] for _ in range(n+1)]

    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b) #그래프 생성
        graph[b].append(a)

    count = 0
    visited = [False]*(n+1)
    for i in range(1,n+1):
        if visited[i] == False:
            bfs(i,graph, visited)
            count += 1
    print(f"#{t} {count}")