[Python][백준/BOJ] 1012번 : 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

내 코드

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

t = int(input())
dx = [1,-1,0,0]
dy = [0,0,1, -1]

def dfs(x, y):
    if x<0 or x>=m or y<0 or y>=n:
        return
    
    if board[x][y]:
        board[x][y]=False
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            dfs(nx, ny)
        return True
    return False

for _ in range(t):
    m, n, k = map(int,input().split())
    cnt =0
    board = [[False]*m for _ in range(n)]
    
    for _ in range(k):
        a, b = map(int, input().split())
        board[b][a] =True
        
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                cnt+=1
    print(cnt)

 

DFS, 붙어있는 것들을 찾아서 개수 세기

개수 세기는 visited를 따로 해줄 필요가 없다. 

만약 1로 표기된 곳을 찾는 것이라면, 한 번 지난 곳은 0으로 바꾸어준다. (visited처럼 방문했다는 의미)

그리고 헷갈리지 말아야 할 것은, 몇번째 row ,몇번째 col 이게 구분이 명확한 곳이라면 

board[row][col]=1만 해주어야 한다.

서로 연결이 되어 있는 곳이라면 board[row][col]=1, board[col][row]=1 둘 다 해주어야 한다.

또한 재귀 돌릴 때, dfs(nx, ny) 해서 바뀐 부분이 계속 재귀함수를 타고 돌도록 해주어야 한다.