[백준] 1012번, 유기농 배추 (Python)

문제

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

1012번: 유기농 배추

 

코드

import collections

t = int(input())

def bfs(x,y):
    queue = collections.deque()
    queue.append((x,y))
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    
    while queue:
        x, y = queue.popleft()
        
        # 주변 4방향을 모두 확인한다.
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and check[nx][ny] == -1:
                    check[nx][ny] = 1
                    queue.append((nx,ny))
    
for i in range(t):
    n, m, k = map(int, input().split())
    graph = [[0]*m for _ in range(n)]
    check = [[-1]*m for _ in range(n)]
    count = 0
    
    for j in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1
    
    # 배추흰지렁이(값이 1인곳)가 있는곳이고 아직 방문하지 않았을경우 bfs를 시작한다.
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 1 and check[x][y] == -1:
                bfs(x,y)
                count += 1
    print(count)

배추흰지렁이가 있는 영역, 즉 값이 1이고 주변(상하좌우)에 이어진곳을 포함하여 한군데이고 모두 몇군데가 있는지 확인하는 문제이다.

 

좌표방식으로 표현해주기 위해서 graph를 0으로 채워진 이중리스트를 선언하고 1인 x,y를 받아서 0을 1로 바꿔주면된다.

 

값이 1이면서 아직 방문하지 않은곳을 모두 bfs로 돌고 count를 세주면 모두 몇군데가 있는지 찾을 수 있다.