[백준/ 파이썬] 1012 유기농 배추

#문제링크

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

1012번: 유기농 배추

#나의풀이

import sys
sys.setrecursionlimit(10**6)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def DFS(x, y):
    board[x][y] = 0
    
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        
        if 0 <= xx < n and 0 <= yy < m and board[xx][yy] == 1:
            DFS(xx, yy)


T = int(sys.stdin.readline())

for _ in range(T):
    n, m, c = map(int, input().split())
    board = [[0]*m for _ in range(n)]
    count = 0
    
    for i in range(c):
        x, y = map(int, input().split())
        board[x][y] = 1
        
    for i in range(n):
        for j in range(m):
        
            if board[i][j] == 1:
                DFS(i, j)
                count += 1
                
    print(count)

#해설

길찾기 같은 dfs, bfs 기본 문제가 아닐까 싶다.

 

입력값을 모두 입력받고 테이블을 0으로 초기화 시키고 배추가 심어진곳은 1로 표시하였다.

테이블 전체를 탐색하면서 배추가 심어졌다면 DFS로 탐색을 하게 되고 count(배추흰지렁이)를 증가 시켜준다.

 

DFS에서 다시 탐색하는것을 방지하기위해 x, y인곳을 0으로 바꾸어준다 이후 4번짜리 반복문으로 dx, dy에 설정된 값으로 동서남북 탐색하게 된다. 

 

배열을 넘어가면 안되므로 조건을 걸어준다 추가로 탐색할 지점이 배열을 넘어가지 않게 설정하고 그 다음 탐색할곳이 1로 배추가 심어졌다면 DFS함수로 값을 다시 넘겨주어 재귀를 실행한다.