[백준] 1012 - 유기농 배추 (dfs 풀이) (python)

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

1012번: 유기농 배추

 

포인트

dfs 혹은 bfs 로 쉽게 풀 수 있는 문제입니다.

대신 두 알고리즘에 대해 잘 모른다면 풀기 어렵기 때문에 모른다면 이 참에 숙지해둡시다

 

탐색 알고리즘 DFS (깊이 우선 탐색) 와 BFS (너비 우선 탐색) (python)

저는 dfs로 풀었습니다

 

코드

	# 백준 채점 시스템의 최대 재귀 깊이는 1000으로 세팅되어있어 10000으로 넉넉히 늘려주는 게 좋습니다.
	import sys
	sys.setrecursionlimit(10000)
	# dfs 함수를 정의합니다.
	def dfs(r, c):
	# 범위를 벗어나거나 배추가 심어져있지 않은 땅이거나 이미 카운트 한 땅은 패스
	if r < 0 or c < 0 or r >= n or c >= m:
	return False
	if ground[r][c] == 0:
	return False
	# 배추가 심어져 있으면
	if ground[r][c] == 1:
	# 중복하여 세지 않도록 0으로 돌려주고 상하좌우로 dfs 재귀 함수 출발
	ground[r][c] = 0
	dfs(r + 1, c)
	dfs(r - 1, c)
	dfs(r, c + 1)
	dfs(r, c - 1)
	# 다 돌고 나면 True 를 리턴하도록합니다
	return True
	return False
	# 테스트 케이스 입력받고
	t = int(input())
	# 그만큼 돌면서
	for _ in range(t):
	answer = 0
	# 가로 세로 갯수 입력받아 2차원 배열로 땅 구성하고
	m, n, k = map(int, input().split())
	ground = [[0 for _ in range(m)] for _ in range(n)]
	# 배추 심어져 있는 위치 표시한 다음
	for _ in range(k):
	x, y = map(int, input().split())
	ground[y][x] = 1
	# 왼쪽 끝 부터 쭉 돌면서 dfs 출발
	for i in range(n):
	for j in range(m):
	# True 를 리턴하는 경우는 그 지점에 배추가 심겨져 있었고 상하좌우까지 모두 확인한 경우란 말이기 때문에
	if dfs(i, j):
	# 영역의 개수를 하나 올려줍니다
	answer += 1
	print(answer)

view raw boj_1012.py hosted with ❤ by GitHub