코테분석#8-1 유기농 배추 (백준 1012번) 😱

1. 문제

2. 나의 풀이

3. 쌤's 풀이

• BFS/DFS 모두로 풀 수가 있는 문제
• flood fill은 전체탐색을 하고 한번 탐색한 것은 다시 탐색하지 않는 것이 핵심!
• BFS/DFS 문제를 풀 때 재귀함수를 쓰는 경우, 파이썬의 재귀스택은 좀작은 편이라 재귀스택이 차서 오류가 날 수도 있다고 한다.

import sys

# 재귀함수에 깊이를 제한하는 방법
sys.setrecursionlimit(10000)

T = int(input())
B, ck = [], []

dx, dy = [1,0,-1,0],[0,1,0,-1]

def dfs(x,y):
	global B, ck
    if ck[x][y] == 1:
    	return
	ck[x][y] = 1
	for i in range(4):
    	xx, yy = x+dx[i], y+dy[i]
        if B[xx][yy] ==0 or ck[xx][yy] == 1:
        	continue
        dfs(xx,yy)

def process():
	global B, ck
	M, N, K =  map(int, input().split())
    B = [[0 for i in range(M+2)] for _in range(N+2)]
    ck = [[0 for i in range(M+2)] for _in range(N+2)]
    for _ in range(K):
    	x, y = map(int, input().split())
        B[Y+1][X+1] = 1
    
    ans = 0
    for i in range(1, M+1):
    	for j in range(1, M+1):
        	if B[i][j] == 0 or ck[i][j] == 1:
            	continue:
            dfs(i,j)
            ans += 1
	print(answer)

for _ in range(T):
	process()

느낀 점

• 와우! 으렵네!