본문 바로가기

알고리즘

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

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

 

 

간단한 그래프 문제이다. 이 다음 문제는 양방향 관련된 문제를 풀고 싶은데. . 찾아봐야겠다.

그리고 이 문제를 풀면서 재귀깊이제한 기본값이 1000으로 제한되어 있는데, 이 문제를 풀 때는 그 조건을 풀어줘야한다..

 

recursionError이 나와서 원인을 찾아보니 재귀깊이를 늘려주니 정답이 되었다.

 

import sys
sys.setrecursionlimit(10**7)


def ps(x,y,arr):
    global n,m

    arr[x][y] = 2
    # print(x,y,n,m)
    if(y < m-1 and arr[x][y+1] == 1):
        ps(x,y+1,arr)

    if ( x < n-1 and arr[x+1][y] == 1):
        ps(x+1, y, arr)

    if (y > 0 and arr[x][y-1] == 1):
        ps(x, y - 1, arr)

    if (x > 0 and arr[x-1][y] == 1):
        ps(x-1, y, arr)

# n = y , m = x

case = int(input())ㅌ

for c in range(0,case):
    n,m,k = map(int,input().split())

    arr = [[0 for i in range(0,m)] for j in range(0,n)]
    # print(arr)
    for i in range(0,k):
        x,y = map(int,input().split())

        arr[x][y] = 1


    cnt = 0
    for i in range(0,n):
        for j in range(0,m):
            if arr[i][j] == 1:
                cnt += 1
                # print(arr)
                ps(i,j,arr)


    print(cnt)

'알고리즘' 카테고리의 다른 글

[백준] 7576번: 토마토  (0) 2022.02.02
[백준] 2178번: 미로 탐색  (0) 2022.01.31
[백준] 1260번: DFS와 BFS  (0) 2022.01.30
[백준] 2606번: 바이러스  (0) 2022.01.27
[Algorithm-swift] 두 개 뽑아서 더하기  (0) 2021.12.28