[백준 1012] 유기농 배추

🍎 [백준 1012] 유기농 배추

문제 링크

⚾ 코드

    import sys
    # 재귀 탐색 깊이 늘려주기
    sys.setrecursionlimit(100000)
    input = sys.stdin.readline

    # 테스트케이스
    T = int(input())
    answer = []
    for _ in range(T):
        M, N, K = map(int, input().split())
        grid = [[0]*(M) for _ in range(N)]
        visited = [[False]*(M) for _ in range(N)]
        count = 0

        for i in range(K):
            x, y = map(int, input().split())
            grid[y][x] = 1

        # 범위 체크
        def check_range(x, y):
            if x >= 0 and x < N and y >= 0 and y < M:
                return True
            return False

        # dfs 함수 구현
        def dfs(x, y):
            dx = [-1, 1, 0, 0]
            dy = [0, 0, -1, 1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if check_range(nx, ny) and grid[nx][ny] == 1 and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    dfs(nx, ny)

        for i in range(N):
            for j in range(M):
                if grid[i][j] == 1 and visited[i][j] == False:
                    visited[i][j] = True
                    dfs(i, j)
                    count += 1

        answer.append(count)

    for i in answer:
        print(i)

🔔 해결과정 & 깨달은 점

• DFS의 아이디어를 활용해 풀었다.
• DFS를 한 번 마치고 오면 count += 1
• 파이썬은 기본 재귀 탐색 깊이가 1000이다. 코딩테스트 시 재귀 함수를 쓴다면 그 깊이를 깊게 해주어야 한다. sys.setrecursionlimit(100000)
• 파이썬 재귀 깊이 sys.setrecursionlimit