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

fooooif·2021년 7월 5일
1
post-thumbnail

✍ 문제


문제링크: https://www.acmicpc.net/problem/1012

👏 풀이과정

간단한 graph 문제이다. dfs함수를 이용하여 재귀용법으로 풀었다.

import sys
sys.setrecursionlimit(10**6)
visited = []
dir_go = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
def dfs(array_list,y,x):
    if [y,x] in visited:
        return
    visited.append([y,x])
    for i in range(4):
        x_1= x + dir_go[i][0]
        y_1 = y + dir_go[i][1]
        if x_1 >= 0 and x_1 <= len(array_list[0]) -1 and y_1 >=0 and y_1 <= len(array_list) -1 and array_list[y_1][x_1] == 1:
            dfs(array_list,y_1,x_1)



T = int(sys.stdin.readline())
for _ in range(T):
    M, N, K = map(int,sys.stdin.readline().split())
    array_list = [[0]* M for _ in range(N)]


    for _ in range(K):
        x , y = map(int,sys.stdin.readline().split())
        array_list[y][x] = 1
    for i in range(N):
        for j in range(M):
            if array_list[i][j] == 1 and [i,j] not in visited:
                cnt += 1
                dfs(array_list,i,j)
    print(cnt)
    cnt = 0
    visited.clear()




profile
열심히 하자

0개의 댓글