[파이썬, Python] 백준 1012: 유기농 배추

문제

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

1012번: 유기농 배추

코드

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

t = int(input())

def bfs(land, a, b):
    queue = deque()
    queue.append((a, b))
    land[a][b] = 0
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if land[nx][ny] == 1:
                land[nx][ny] = 0
                queue.append((nx, ny))
    return

for i in range(t):
    cnt = 0
    n, m, k = map(int, input().split())
    land = list(list(0 for i in range(m))for i in range(n))

    for i in range(k):
        x, y = map(int, input().split())
        land[x][y] = 1

    for a in range(n):
        for b in range(m):
            if land[a][b] == 1:
                bfs(land, a, b)
                cnt += 1

    print(cnt)

설명

우선 land에 대한 정보를 입력받아서, land를 만들어준다.

n과 m의 범위 내에 있는 각 a, b에 대해서 만약 land[a][b]가 1이라면,
bfs를 실행한다.

bfs에서 queue의 경우 deque을 사용했다.
queue에 입력받은 a와 b를 넣어주고,
land[a][b]를 0으로 만들어준다.(방문 처리)

queue가 있으면 4방향에 대해 탐색을 한다.
범위를 벗어나는 수에 대해선 건너뛰고(0 이하 혹은 n, m 이상)
탐색 중에 1인 땅을 만나면, 그 수를 queue에 넣어주고 탐색을 추가로 진행한다.

탐색을 모두 마쳤다면(연결되어 있는 땅이 더 이상 없다면)
cnt를 1 올리고 남은 범위에 대해 추가로 탐색을 진행한다.