[백준 1012번] 유기농 배추

 

# 개강전 마지막 백준..

# 다음학기 알고리즘을 좀 더 배우게 되면 공부와 백준을 같이해보자!

 

-- 정답코드

import sys
sys.setrecursionlimit(10**6)

T = int(sys.stdin.readline()) # 테스트 케이스의 개수

# 상하좌우가 붙어있는 그룹 count!

# 재귀함수를 이용
def check_group(x, y):
    if x < 0 or x >= M or y < 0 or y >= N:
        return
    if [x,y] in cabbage:
        cabbage.remove([x,y])
    else:
        return
    check_group(x + 1, y)
    check_group(x, y+1)
    check_group(x-1, y)
    check_group(x, y-1)

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split()) # 가로길이, 세로길이, 배추 위치 개수
    cabbage = []
    count = 0 # 배추흰지렁이의 개수

    for _ in range(K): # cabbage list 만들기
        a, b = map(int, sys.stdin.readline().split())
        cabbage.append([a,b])

    while cabbage: # cabbage 리스트가 존재하는 한
        check_group(cabbage[0][0],cabbage[0][1])
        count += 1
    print(count)

처음에는 DFS, BFS 방법을 통해 문제를 풀려 노력했는데 결국은 재귀함수를 이용해 풀었다. ( 물론 DFS, BFS 방법으로도 풀 수 있는 듯 하다..)

재귀함수를 이용할 때 setrecursionlimit를 상한시켜 기본 반복인 횟수인 1000보다 큰 수를 입력해주어야한다. ( 간혹 재귀의 건수가 적어 답이 잘못나온다고 한다..)

 

기본적인 풀이방법은 입력받은 배추의 위치 좌표를 list로 담아 check_group을 통해 시작점에서 부터 이어진 한 그룹을 지우고 count + 1을 하는 방식으로 전체에 필요한 배추흰지렁이의 개수를 찾았다.

 

요즘에 따로하는 공부, 알바, 과외 때문에 백준을 소홀히 하였는데 개강 후에도 가능한만큼 문제 풀이에 도전해보겠다.

 

 

오늘도 성공적으로 필요한 배추흰지렁이의 개수를 찾아내었다.