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

1012번: 유기농 배추

 

>문제

>접근방법

   2차원 리스트에 밭을 구현하고 배추를 심은 곳에만 1을 넣는다. 1인 곳에서 상하좌우를 탐색해서 배추흰지렁이 마리 수 세기.

 

 

>풀이법

   1. 밭의 크기만큼 2차원 리스트를 생성한다.

   2.입력받은 배추 위치에 1을 넣어준다.

   3.  밭을 반복문으로 인덱스 하나씩 검색해서 1인 경우에 search함수를 실행한다.

   4. search함수는 1의 상하 좌우가 0 일 때까지 재귀적으로 탐색하고, 탐색이 끝난 자리는 0으로 값을 변경해준다.

   5. search가 한 번 수행될 때마다 배추흰지렁이(count)의 개수를 하나씩 더해준다.

* 이때 런타임 에러 (RecursionError) 가 발생하는데 sys.setrecursionlimit(10**6) 을 입력해주면 오류없이 수행된다.

 

 

>코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())

def search(x, y):
    if x < 0 or y < 0 or x >= c or y >= r:
        return

    if graph[x][y] == 0:
        return    
    graph[x][y] = 0

    search(x-1, y)
    search(x+1, y)
    search(x, y-1)
    search(x, y+1)

for _ in range(n):
    r, c, num = map(int, input().split())
    graph = [[0]*r for _ in range(c+1)]
    count = 0

    for _ in range(num):
        row, col = map(int, input().split())
        graph[col][row] = 1
        
    # dfs
    for i in range(c): #세로
        for j in range(r): #가로
            if graph[i][j] == 1:
                search(i, j)
                count += 1
    print(count)

 

 

>결과

 

 

>결론 

비빔냉면 먹어야징 히히