[10/12] 1012 (유기농 배추)

레벨2 문제
DFS/BFS

내 코드 (BFS)

from collections import deque

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1

    # 동서남북
    move_h = [-1, 1, 0, 0]
    move_w = [0, 0, -1, 1]

    # 사방으로 삐져나가는 거 잘 체크하기
    def bfs(h, w):
        queue = deque([])
        queue.append([h, w])

        while queue:

            temp = queue.popleft()
            c, d = temp[0], temp[1]

            for i in range(4):
                temp_h = c + move_h[i]
                temp_w = d + move_w[i]

                # 선을 안넘고 1이어야함
                if ( 0<=temp_h<n and 0<=temp_w<m and graph[temp_h][temp_w] == 1):
                    queue.append([temp_h, temp_w])
                    graph[temp_h][temp_w] = 0

    cnt = 0
    for h in range(n):
        for w in range(m):
            if ( graph[h][w] == 1 ):
                graph[h][w] = 0
                bfs(h, w)
                cnt += 1

    print(cnt)

내 코드 (DFS)

from collections import deque

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1

    # 동서남북
    move_h = [-1, 1, 0, 0]
    move_w = [0, 0, -1, 1]

    def dfs(h, w):
        
        for i in range(4):
            temp_h = h + move_h[i]
            temp_w = w + move_w[i]
            
            if ( 0 <= temp_h < n and 0 <= temp_w < m and graph[temp_h][temp_w] == 1 ):
                graph[temp_h][temp_w] = 0
                dfs(temp_h, temp_w)

    cnt = 0
    for h in range(n):
        for w in range(m):
            if ( graph[h][w] == 1 ):
                graph[h][w] = 0
                dfs(h, w)
                cnt += 1

    print(cnt)

로직

• BFS / DFS (2차원 그래프)