백준 유기농 배추 1012 파이썬

문제

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

문제 요약

입력

테스트 케이스 개수 T

배추밭 가로 길이 M, 배추 세로 길이 N, 배추 위치 개수 K

배추의 위치 X Y

예제

입력

출력

6

 

 

입력

출력

2

 

슈도 코드

DFS를 활용해서 풀 수 있다.

1. 특정 지점 상, 하, 좌, 우를 살펴본다
2. 주변 지점 중 값이 ‘1’이면서 방문하지 않은 지점이 있으면 해당 지점을 방문한다
3. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보며 방문을 진행하는 과정을 반복한다
4. 1, 2번의 과정을 반복하며, 방문하지 않은 지점 수를 카운트 한다.

제출 코드

import sys
sys.setrecursionlimit(10000)

def dfs(x, y, graph):
    if x <= -1 or x >= w or y <= -1 or y >= h:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x-1, y, graph)
        dfs(x+1, y, graph)
        dfs(x, y-1, graph)
        dfs(x, y+1, graph)
        return True
    return False


t = int(sys.stdin.readline())
for _ in range(t):
    w, h, k = map(int, sys.stdin.readline().split())
    graph = [[0] * h for _ in range(w)]

    for _ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[a][b] = 1

    result = 0
    for i in range(w):
        for j in range(h):
            if dfs(i,j, graph):
                result += 1
    print(result)

 

배운점

런타임 에러 (recursion error)

파이썬에서 1000번 이상의 recursion이 발생 시 뜨는 에러

→ sys.setrecursionlimit(10000) 추가하기