[백준] 1012번: 유기농 배추 -python 답안 (파이썬)

문제 링크: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

단계: 실버2

알고리즘 분류: 

- 그래프 이론, 그래프 탐색, 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)

 

python 파이썬 답압:

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def dfs(x,y):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    for i in range(4):
        xx = x + dx[i] 
        yy = y + dy[i]
        if (0<=xx <m) and (0<=yy<n):
            if g[yy][xx] ==1: # 배추 있고, 안지나감
                g[yy][xx] =-1 # 지나감
                dfs(xx,yy)

            
T = int(input())
for i in range(T):
    m,n,k = map(int, input().split())
    # graph 생성
    g = [[0]*m for _ in range(n)]
    # 배추 있는 곳 표시
    for i in range(k):
        x, y = map(int, input().split())
        g[y][x] =1
    # 정답 세기
    count =0 
    for x in range(m):
        for y in range(n):
            if g[y][x] ==1:
                count+=1
                dfs(x,y)
    print(count)