[Baekjoon] 1012번 : 유기농 배추(Python)

Python

방법 1 - 메모리 33224KB / 시간 88ms / 코드 길이 770B

DFS를 활용한 방법이다.

일반적인 DFS 코드와 유사하므로 조건에 부합하도록 DFS를 진행하면 된다.

2차원 list를 거닐 때를 위한 dx, dy에 따라 움직이고 이에 맞는 새로운 nx, ny 값으로 재귀를 사용한다.

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
t = int(input())

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

def dfs(x,y):
    if x < 0 or x > m - 1 or y < 0 or y > n - 1:
        return False

    if l[x][y]:
        l[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > m-1 or ny < 0 or ny > n-1:
                continue
            dfs(nx, ny)
        return True
    return False

for v in range(t):
    m,n,k = map(int, input().split())
    l=[[0]*n for _ in range(m)]
    for i in range(k):
        a,b = map(int, input().split())
        l[a][b] = 1

    cnt = 0
    for i in range(m):
        for j in range(n):
            if l[i][j]:
                cnt += dfs(i,j)
    print(cnt)

방법 2 - 메모리 32436KB / 시간 104ms / 코드 길이 807B

BFS를 활용한 방법이다.

일반적인 BFS 코드와 유사하므로 조건에 부합하도록 BFS를 진행하면 된다.

deque를 활용하여 append하고 popleft를 통해 제외시킨다.

from collections import deque
import sys
input = sys.stdin.readline
t = int(input())

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

def bfs(x,y):
    q = deque()
    q.append((x,y))
    l[x][y]=0

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

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

            if nx < 0 or nx > m-1 or ny < 0 or ny > n-1:
                continue

            if l[nx][ny]:
                l[nx][ny]=0
                q.append((nx,ny))
    return True

for v in range(t):
    m, n, k = map(int, input().split())
    l = [[0] * n for _ in range(m)]
    for i in range(k):
        a, b = map(int, input().split())
        l[a][b] = 1

    cnt = 0
    for i in range(m):
        for j in range(n):
            if l[i][j]:
                cnt += bfs(i, j)
    print(cnt)