1012 - 유기농 배추 (silver 2)

"""
1012 - 유기농 배추 (silver 2)
"""
import sys

input = sys.stdin.readline


def dfs(array, i, j):
    array[i][j] = 2
    if j + 1 <= M - 1 and array[i][j + 1] == 1:
        dfs(array, i, j + 1)
    if i + 1 <= N - 1 and array[i + 1][j] == 1:
        dfs(array, i + 1, j)


T = int(input().rstrip())

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

    for _ in range(K):
        X, Y = map(int, input().split())
        array[Y][X] = 1

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

- 1차 틀림

"""
1012 - 유기농 배추 (silver 2)
"""
import sys

input = sys.stdin.readline


def search(array, i, j):
    array[i][j] = 2
    if i - 1 >= 0 and array[i - 1][j] == 1:
        search(array, i + 1, j)
    if i + 1 <= N - 1 and array[i + 1][j] == 1:
        search(array, i + 1, j)
    if j - 1 >= 0 and array[i][j - 1] == 1:
        search(array, i, j - 1)
    if j + 1 <= M - 1 and array[i][j + 1] == 1:
        search(array, i, j + 1)


T = int(input().rstrip())

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

    for _ in range(K):
        X, Y = map(int, input().split())
        array[Y][X] = 1

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

- 2차 런타임 에러(index error)

"""
1012 - 유기농 배추 (silver 2)
"""
import sys

input = sys.stdin.readline


def bfs(array, i, j):
    queue = [[i, j]]
    qx = [0, -1, 1, 0]
    qy = [1, 0, 0, -1]
    while queue:
        a = queue[-1][0]
        b = queue[-1][1]
        array[a][b] = 2
        del queue[-1]
        for k in range(4):
            q = a + qx[k]
            w = b + qy[k]
            if 0 <= q < N and 0 <= w < M and array[q][w] == 1:
                queue.append([q, w])


T = int(input().rstrip())

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

    for _ in range(K):
        X, Y = map(int, input().split())
        array[Y][X] = 1

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

BFS 알고리즘

- 문제 접근 방식은 맞음

- bfs 함수 코드 이해하기