[boj] 백준 1012 유기농 배추 python 풀이

대표적인 섬 찾기 bfs 문제. MAP 자체에 visited를 2 표시해서 풀이함. 0으로 표시할걸.. 생각이 짧았다

 

문제

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

 

풀이

import sys
import collections
input = sys.stdin.readline

move = [(-1,0),(0,1),(1,0),(0,-1)]

def bfs(i,j,MAP):
    q = collections.deque()
    q.append((i,j))
    MAP[i][j] = 2 #visited

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

        for tx,ty in move:
            nx = x + tx
            ny = y + ty

            if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 1:
                q.append((nx,ny))
                MAP[nx][ny] = 2 # visited

def find_island(MAP):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if MAP[i][j] == 1:
                bfs(i,j,MAP)
                cnt += 1

    return cnt

T = int(input().strip())
for _ in range(T):
    M, N, K = map(int,input().split())
    MAP = [[0 for _ in range(M)] for _ in range(N)]
    for _ in range(K):
        X,Y = map(int,input().split())

        MAP[Y][X] = 1

    print(find_island(MAP))