[백준 1012] [dfs/bfs] 유기농 배추

💻 백준 1012번 [유기농 배추]

1012번: 유기농 배추

풀이)

import sys
sys.setrecursionlimit(100000000)

T = int(input())
cnt_lst = []
for t in range(T) :
    m,n,k = map(int,input().split())
    cab = [list(map(int,input().split())) for _ in range(k)]

    map_ = [[0]*m for _ in range(n)]
    for i,j in cab : 
        map_[j][i] = 1
    visited = [[0]*m for _ in range(n)]
    def dfs(x,y,visited) :
        # 1. 방문한 노드인지 확인
        if not visited[x][y] :
            # 방문처리
            visited[x][y] = 1
            if map_[x][y] == 0 : return False
            # 2. 인접노드 순회
            for [i,j] in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]] :
                if 0 <= i <= n-1 and 0 <= j <= m-1 :
                    if map_[i][j] == 1 and not visited[i][j]: 
                        dfs(i,j,visited)
                    elif map_[i][j] == 0 :
                        visited[i][j] = 1   

        return True

    cnt = 0 
    for i in range(n) :
        for j in range(m) :
            if not visited[i][j] : 
                bool_ = dfs(i,j,visited) 
                if bool_ : cnt+=1
    cnt_lst.append(cnt)
print(*cnt_lst,sep='\n')

 

메모리	시간	언어	코드길이
32148KB	404ms	Python 3	1004B

 

과정)

처음 제출했을 때 런타임에러(recursion error)가 발생하여

맨 위에 두줄을 추가해주었다

import sys
sys.setrecursionlimit(100000000)