백준_1012_유기농 배추_dfs_bfs_파이썬

문제 링크

1012번: 유기농 배추

 

 

def bfs(row,col):
    score = 0
    if map1[row][col] ==1:
        score+=1
        map1[row][col] = 0
        now_point = [(row,col)]
        while len(now_point)!= 0:
            now_row, now_col = now_point.pop(0)
            for i in range(4):
                now_x = now_row+dx[i]
                now_y = now_col+dy[i]
                if -1<now_x<row_num and -1<now_y<col_num:
                    if map1[now_x][now_y] == 1:
                        score+=1
                        map1[now_x][now_y] = 0
                        now_point.append((now_x,now_y))
    return score 
 
def dfs(row,col):
    global score
    if map1[row][col] ==1:
        score +=1
        map1[row][col] = 0
        for i in range(4):
            now_x = row+dx[i]
            now_y = col+dy[i]
            if -1<now_x<row_num and -1<now_y<col_num:
                dfs(now_x,now_y)
    return score
 
dx = [1,-1,0,0]
dy = [0,0,1,-1]
 
test_case = int(input())
for test in range(test_case):
    score = 0
    ans = 0
    row_num, col_num, cab_num = map(int,input().split())
    map1 = [[0 for _ in range(col_num)] for _ in range(row_num)]
    for i in range(cab_num):
        row,col = map(int,input().split())
        map1[row][col] = 1
    for i in range(row_num):
        for k in range(col_num):
            now_score = bfs(i,k)
            if now_score != 0:
                ans+=1
                score = 0
    print(ans)

 

 

Be positive!

Be rich!

Live your life!