문제 출처 : https://www.acmicpc.net/problem/1012
난이도 : 실버 2

문제 파악

배추가 군데군데 심어져 있고, 상/하/좌/우로 인접한 배추들은 한 덩어리(군집)로 본다.
배추흰지렁이 1마리가 어떤 배추에 살고 있으면 인접한 배추들로 이동 가능하니까,
배추들이 “몇 덩어리로 나뉘어 있는지” 즉 연결된 컴포넌트 개수를 세어 출력해야 한다.

해답 및 풀이

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y): # x,y를 받아 상하좌우 BFS로 끝까지 탐색하는 함수

    queue = deque()
    queue.append((x,y))

    graph[y][x] = 0 # 방문 처리

    while queue:
        x, y = queue.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            # nx, ny 가 범위내에 존재하고, 값이 1이라면 큐에 넣기
            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 1:
                queue.append((nx,ny))
                graph[ny][nx] = 0

T = int(input())

for _ in range(T):
    M, N, K = map(int,input().split())

    graph = [ 
    [0 for _ in range(M)] for _ in range(N)
    ]
    # 우리가 원하는 그래프 형태        
    # [ 
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0],
    # [0,0,0,0,0,0,0,0,0,0]
    # ]        
            

    # X, Y 좌표에 1 채우기
    for _ in range(K):
        X, Y = map(int,input().split())
        graph[Y][X] = 1 # Y,X로 해주어야 옳게 들어감

    # graph
    # [
    # [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    # [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    # [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    # [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    # [0, 0, 1, 1, 0, 0, 0, 1, 1, 1], 
    # [0, 0, 0, 0, 1, 0, 0, 1, 1, 1], 
    # [0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    # ]

    # 상하좌우 탐색하여 count 값 늘이기

    
    # vistied 배열은 안쓰고, graph 자체를 1->0으로 바꿔 방문 처리

    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                bfs(j, i)
                count +=1
    print(count)

그래프의 입력을 받는 로직과,
x,y를 graph[y][x]로 바꾸어 넣어야 하는 것,
방향벡터를 활용한 상하좌우 탐색을 공부해볼 수 있었다.

다음날 다시 푼 코드

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(X,Y):
    queue = deque()
    queue.append((X,Y))
    
    while queue:
        x, y = queue.popleft()
        graph[y][x] = 0 # 방문 처리

        # 상하좌우 탐색
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 1: # nx,ny를 방문하지 않았다면
                graph[ny][nx] = 0 # 방문 처리
                queue.append((nx,ny))

T = int(input())


for _ in range(T):
    M,N,K = map(int,input().split())
    cnt = 0
    graph = [ 
    [0] * M for _ in range(N)
    ]

    for _ in range(K):
        X, Y = map(int,input().split())
        graph[Y][X] = 1
    
    for i in range(M):
        for j in range(N):
            if graph[j][i] == 1:
                bfs(i,j)
                cnt += 1
    print(cnt)