백준 1012 - 유기농 배추( Python ) - DFS

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

1012번: 유기농 배추

 

dfs...bfs....어렵다 어려워

알고리즘 오픈 카톡방에 물어보니 24444, 1012, 7569문제로 기본을 쌓아보라는 추천받아서

주말동안 풀긴 풀었다

한문제당 한시간은 안걸린게 다행이였을까~?

 

여튼 이제는 조금 아주 조금은 감이 잡히는 것 같다

 

recursionError 가 발생해서 재귀깊이 제한해주는 코드를 추가해야 통과 할 수 있다.

이외에는 이코테에서 학습한 DFS코드와 동일하게 풀 수 있었다.

[Algorithm] - 탐색 알고리즘 - DFS / BFS

 

import sys
# 백준 서버의 채귀 깊이 제한을 변경해주는 코드 
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# bfs 재귀 함수 구현 
def bfs(x,y):
	# 주어진 범위를 넘어가는 경우 false return 후 함수 종료
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
        
    # 배추가 심어진 1을 만나는 경우 
    if graph[x][y] == 1:
    	# 0으로 변경 ( 일종의 방문 처리 )
        graph[x][y] = 0
        
        # 상하좌우 확인하면서 다시 함수 호출 
        bfs(x + 1, y)
        bfs(x - 1, y)
        bfs(x, y + 1)
        bfs(x, y - 1)
        return True
    # 1이 아닌 다른 모든 경우는 False
    return False
    

t = int(input())

for _ in range(t):
    m,n,k = map(int, input().split())

    graph = [[0] * m for _ in range(n)]

    for _ in range(k):
        x, y = map(int,input().split())
        
        # 주의!!!!!! x,y로 했다가 도대체 왜 틀린지 몰라서 헤맴....
        # 가로가 m이고 세로가 n이다. 익숙함에 속아버림
        graph[y][x] = 1
    
    result = 0
    for i in range(n):
        for j in range(m):
            if bfs(i,j) == True:
                result += 1
                
    print(result)