백준 1012번: 유기농 배추

유형 : BFS
난이도 : 실버 2
https://www.acmicpc.net/problem/1012

문제 접근

해당 문제는 인접 벡터가 주어진 DFS 또는 BFS 를 활용하는 문제이다.
필자는 BFS가 더 약하기에 BFS로 풀겠다.

배추가 심어진 위치(1)를 기준으로 상하좌우로 연결된 배추들을 하나의 덩어리로 본다.
각 덩어리를 BFS 탐색하며 방문 처리하고, 덩어리 수를 count로 세면 된다.
문제에서 배추 위치를 (x, y)로 주지만, graph[y][x]로 접근해야 하는 점에 주의해야한다.

해답 및 풀이

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

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    graph[y][x] = 0  # 방문처리,  문제에서 (x, y) 로 입력이 주어지면 graph[y][x]가 맞다.

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

        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:
                graph[ny][nx] = 0
                queue.append((nx,ny))
T = int(input())

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

    for _ in range(N):
        row = [0] * M
        graph.append(row)

    for _ in range(K):
        x, y = map(int,input().split())
        graph[y][x] = 1
    
    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                bfs(j, i)
                count +=1

    print(count)
        

테스트 케이스가 T번이면
for _ in range(T): 안에 입력문과 그래프를 생성해주고 bfs도 그 안에서 호출해주고 출력도 해주면 된다는 것을 배웠다.