유기농 배추

풀이

dfs 문제를 풀기위해 백준에서 dfs 카테고리로 문제를 찾았고 유기농 배추를 맞이했다.
보통 N,M의 방식으로 줄텐데 여긴 왜 M,N으로 주는지 모르겠지만, 잘 받고 코드에 입력했다.

해당 문제는 bfs또는 dfs로 풀 수 있는데 우선 dfs로 먼저 풀어봤고 아래처럼 풀었다.

입력값 받기
1. board와 visited 생성 및 몇 개의 군락이 있는지 확인할 count 변수 생성
2. 위치를 순회하면서, 배추가 있고, 해당 배추를 확인하지도 않았다면, dfs를 진행!
3. dfs 함수 내에서 stack을 생성하고, 이 stack을 이용해서 진행 -> stack에 값이 존재하는 동안 해당 위치에서 4방향을 확인하고, 해당 위치에 배추가 있고, 확인 안했으면, 계속해서 진행 하는 방식으로 사용.
4. dfs함수가 끝나면, 해당 배추와 인접한 모든 배추는 확인햇으니, visited를 통해 위치 순회 확인에서 걸리지 않기 때문에 count += 1해주기

import sys

# 상하좌우
dr = [-1,1,0,0]
dc = [0,0,-1,1]

def dfs(board, visited, row, column):
    stack = [(row, column)]
    visited[row][column] = 1
    while (stack):
        row, column = stack.pop()
        for i in range(4):
            cr = row + dr[i]
            cc = column + dc[i]
            if 0 <= cr < N and 0 <= cc < M and not visited[cr][cc] and board[cr][cc] == 1:
                stack.append((cr, cc))
                visited[cr][cc] = 1

T = int(sys.stdin.readline())
for testcase in range(1, T+1):
    M, N, K = map(int, sys.stdin.readline().split())
    board = [[0]*M for _ in range(N)]
    visited = [[0]*M for _ in range(N)]
    count = 0
    for _ in range(K):
        A, B = map(int, sys.stdin.readline().split())
        board[B][A] = 1
    for row in range(N):
        for column in range(M):
            if not visited[row][column] and board[row][column] == 1:
                dfs(board, visited, row, column)
                count += 1
    
    # 상하좌우
    dr = [-1,1,0,0]
    dc = [0,0,-1,1]

    print(f'{count}')