💡 [BOJ 1012] 유기농 배추

문제) https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

[내 풀이]

import sys

# 재귀 제한(BOJ default 1000) 확장
sys.setrecursionlimit(10**9)

# 첫줄 테이스케이스 개수 및 정보 입력
T = int(sys.stdin.readline())

for t in range(T):    
    M, N, K = map(int, sys.stdin.readline().split(" "))

    # table 초기화
    table = [[0 for x in range(M)] for y in range(N)]

    # table 구성
    for i in range(K):
        x, y = map(int, sys.stdin.readline().split(" "))
        table[y][x] = 1

    # 상하좌우 탐색 함수 정의
    def search(x, y):
        global table
        table[y][x] = 0
        if (x - 1 >= 0 and table[y][x - 1] == 1):	search(x - 1, y)
        if (y - 1 >= 0 and table[y - 1][x] == 1):	search(x, y - 1)
        if (x + 1 < M and table[y][x + 1] == 1):	search(x + 1, y)
        if (y + 1 < N and table[y + 1][x] == 1):	search(x, y + 1)
        
    # table 조회 및 탐색 실행
    worm = 0
    for x in range(M):
        for y in range(N):
            if table[y][x] == 0: continue
            else:
                worm += 1
                search(x, y)

    sys.stdout.write(f'{worm}\n')

 

[Comment]

크게 어려운 알고리즘 활용 없이, 문제의 설명을 충실히 따랐습니다.

테스트 횟수 T 입력받아 T만큼 반복

    - 행의 갯수 M, 열의 갯수 N, 배추의 갯수 K를 입력받는다.

    - M*N 이차원 리스트 table을 구성, 0으로 초기화

    - K만큼 반복

        - 배추의 좌표 입력받고 table에 1 대입

    - 상하좌우를 재귀 탐색하는 함수 search 정의

    - (0, 0) (좌측상단)좌표부터 (N - 1, M - 1) (우측하단)좌표까지 탐색하며 table값이 1일 경우 search함수 호출하고 worm++

    - worm(지렁이 마릿수) 출력