백준 1012

땅에 존재하는 연속된 배추 묶음의 개수를 구하는 문제이다.

2차원 배열 문제라 바로 DFS/BFS를 떠올렸고,
DFS의 기본적인 틀만 생각해서 문제를 풀었다.

코드(정답)는 다음과 같다.

# 1012

import sys
sys.setrecursionlimit(10000)

def dfs(x, y):
    # 1. 탐색 범위를 벗어나는 경우
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    
    # 2. 탐색 범위를 벗어나지 않는 경우
    # 2-1. 배추가 있는 경우
    if graph[x][y] == 1:
        graph[x][y] = 0

        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)

        return True
    
    # 2-2. 배추가 없는 경우
    return False


t = int(sys.stdin.readline())
for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().split())

    graph = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        x, y = map(int, sys.stdin.readline().split())
        graph[y][x] = 1
    
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                dfs(i, j)
                cnt += 1
    
    print(cnt)

2차원 배열에서의 인덱스와 좌표평면에서의 2차원 좌표가 다르기 때문에,
그래프 문제에선 이 부분을 헷갈리지 않는 게 중요한 것 같다.