백준 실버2 1012. 유기농 배추 (python)

유기농 배추

 

풀이

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}')