2025년 2학기 5주차 C언어

from collections import deque
import sys
input = sys.stdin.readline

n = int(input().strip()) #컴퓨터 숫자
line = int(input().strip()) #간선으로 연결된 숫자

graph = [] #그래프를 초기화
for i in range(n+1):
    graph.append([])

for _ in range(line):
    x, y =map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

#BFS탐색을 시작한다
visited = [False]*(n+1)
q = deque([1]) #1번부터 시작하니 감염으로 설정
visited[1] = True # 위와 동일
count = 0

while q:
    now = q.popleft()
    for check in graph[now]:
        if not visited[check]:
            visited[check] = True
            q.append(check)
            count += 1

print(count)

from collections import deque
import sys
input = sys.stdin.readline

# 방향 벡터 
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(x, y, graph, visited, n, m):
    q = deque([(x, y)])
    visited[y][x] = True
    #배추가 얼마나 있는지 확인한다

    while q:
        cx, cy = q.popleft()
        #for문에서 상하좌우를 확인한다
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # 범위 안, 배추 있음, 아직 방문 안함
            if 0 <= nx < m and 0 <= ny < n:
                if graph[ny][nx] == 1 and not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((nx, ny))


t = int(input().strip())  # 테스트 케이스 수

for _ in range(t):
    m, n, k = map(int, input().split())  # 가로, 세로, 배추 수

    # 밭 초기화
    graph = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]

    # 배추 심기
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    count = 0 #지렁이의 숫자다
    for y in range(n):
        for x in range(m):
        
            if graph[y][x] == 1 and not visited[y][x]:
            #지렁이가 없는 배추 군집일 시 배추가 얼마나 있는 지 확인
                bfs(x, y, graph, visited, n, m)
                #지렁이가 추가된다
                count += 1

    print(count)