백준 1012번: 유기농 배추 - 실버 2

✔ 풀이

2차원 리스트 land를 반복하며 해당 위치의 값이 1일때 그 위치를 기준으로 dfs탐색한다. 값이 1인 곳을 방문하면 값을 0으로 변경하여 다시 방문하지 않도록 한다. dfs탐색이 끝나면 배추 흰 지렁이 개수를 1 증가 시킨다.

✔ 구현 코드1 (recursion)

import sys
sys.setrecursionlimit(10**6)

def dfs(land, i, j):
    if i < 0 or i >= N or j < 0 or j >= M or land[i][j] != 1:
        return
    land[i][j] = 0

    for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]: #상하좌우 이동
        dfs(land, i + di, j + dj)


for _ in range(int(input())):
    M, N, n = map(int, input().split())  #가로, 세로, 배추 개수
    land = [[0] * M for _ in range(N)]
    #land 구현
    for _ in range(n):
        j, i = map(int, input().split())
        land[i][j] = 1
    #배추흰지렁이 개수 count
    cnt = 0
    for i in range(N):
        for j in range(M):
            if land[i][j] == 1:
                dfs(land, i, j)
                cnt += 1
    print(cnt)

✔ 구현 코드2 (stack)

def dfs(land, i, j):
    visited = [(i, j)]
    stack = [(i, j)]
    while stack:
        i, j = stack.pop()
        land[i][j] = 0
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_i, next_j = i + di, j + dj
            if (0 <= next_i < N) and (0 <= next_j < M) and (next_i, next_j) not in visited and land[next_i][next_j] == 1:
                stack.append((next_i, next_j))
                visited.append((next_i, next_j))


for _ in range(int(input())):
    M, N, n = map(int, input().split())  #가로, 세로, 배추 개수
    land = [[0] * M for _ in range(N)]
    #land 구현
    for _ in range(n):
        j, i = map(int, input().split())
        land[i][j] = 1
    #배추흰지렁이 개수 count
    cnt = 0
    for i in range(N):
        for j in range(M):
            if land[i][j] == 1:
                dfs(land, i, j)
                cnt += 1
    print(cnt)