💡 [BOJ 1012] 유기농 배추

목차

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

1012번: 유기농 배추

 

[내 풀이]

python

닫기 줄바꿈

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(지렁이 마릿수) 출력