[백준 파이썬] # 1012 유기농 배추 (BFS 풀이)

Silver II

# 1012 유기농 배추 (BFS)

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

1012번: 유기농 배추

 

풀이 (BFS)

from collections import deque

def bfs(x, y):
    queue = deque()
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    if graph[y][x] == 1:
        queue.append((x, y))
        visited[y][x] = True
        cnt = 1

        while queue:
            x, y = queue.popleft()

            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if visited[ny][nx] == False and graph[ny][nx] == 1:
                        visited[ny][nx] = True
                        queue.append((nx,ny))
                        cnt += 1

    return cnt


T = int(input())

for i in range(T):
    M, N, K = map(int, input().split())
    graph = [[0]*M for i in range(N)]
    visited = [[False]*M for i in range(N)]
    li = []

    for i in range(K):
        a, b = map(int, input().split())
        graph[b][a] = 1

    for i in range(M):
        for j in range(N):
            if graph[j][i] == 1 and visited[j][i] == False:
                li.append(bfs(i, j))


    print(len(li))

 

풀이 후기

• 풀이 구조에 조금 익숙해져서 인지 스스로 풀었지만 아직 과정이 많이 헷갈린다
• 2667 단지번호붙이기 문제에서 행, 열 구조에 대해서 조금 더 이해한다면 풀 수 있을 문제다