Jinho Tech

기본적인 DFS & BFS 문제이다.

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x):
    graph[y][x] = 0
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < N) and (0 <= X < M) and graph[Y][X] == 1:
            dfs(Y, X)

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

BFS 풀이

from collections import deque

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < M) and graph[Y][X] == 1:
                queue.append((Y, X))
                graph[Y][X] = 0
                           
for case in range(int(input())):
    M, N, K = map(int, input().split())
    graph = [[0]*M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1
    res = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                graph[i][j] = 0
                bfs(i, j)
                res += 1
    print(res)