[Python] BOJ(백준) 1012번 - 유기농 배추

1. 링크

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

2. 난이도(solved.ac 참고)

실버2

3. 풀이

	# https://www.acmicpc.net/problem/1012
	import sys
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	def dfs(x, y):
	for i in range(4):
	new_x = x + dx[i]
	new_y = y + dy[i]
	if 0 <= new_x < n and 0 <= new_y < m: # 범위 검사
	if matrix[new_x][new_y] == 1:
	matrix[new_x][new_y] = 2
	dfs(new_x, new_y)
	t = int(input())
	for _ in range(t):
	m, n, k = map(int, sys.stdin.readline().split())
	matrix = [[0 for _ in range(m)] for _ in range(n)]
	# input 받고 행렬 생성
	for i in range(k):
	a, b = map(int, sys.stdin.readline().split())
	matrix[b][a] = 1
	count = 0
	for i in range(n):
	for j in range(m):
	if matrix[i][j] == 1:
	dfs(i, j)
	count += 1
	print(count)

view raw 유기농배추.py hosted with ❤ by GitHub

 

이렇게 좌표 형태로 나타난 문제는, dfs에서 x좌표와 y좌표를 구해준 뒤에 재귀 형태로 둔다. 그 다음, 테스트 케이스 횟수인 t회 도는 반복문 내부에서 input 받고 빈 행렬 만들고, a, b 입력받은 뒤에 넣어주고, 2중 for문을 통해 전체 행렬을 돌면서 값이 1인 부분을 조사한 뒤에 1이면 dfs 처리한다.