(Python/🥈2)백준 알고리즘 1012번: 유기농 배추

문제 출처: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

풀이:

 

import sys
from collections import deque

T = int(input())
move = [(0,1),(0,-1),(1,0),(-1,0)]
 # 가로 세로 K갯수
def bfs(a,b):
    Q = deque([(a,b)])
    visited[a][b] = 0 # 1을 0 으로 방문했음
    while Q:
        x,y = Q.popleft()
        for sx, sy in move:
            dx, dy = x + sx, y + sy
            if dx < 0 or dx >= N or dy < 0 or dy >= M:
                continue
            if visited[dx][dy] == 1:
                Q.append((dx,dy))
                visited[dx][dy] = 0

for i in range(T):
    M, N, K = map(int,input().split())
    visited = [[0]*(M) for _ in range(N)]
    cnt = 0
    for j in range(K):
        x, y = map(int, input().split(" "))
        visited[y][x] = 1

    for a in range(N):
        for b in range(M):
            if visited[a][b] == 1:
                bfs(a,b)
                cnt += 1

    print(cnt)

 

한 번 bfs가 실행될때 마다 카운트를 1 늘리면 된다.

for j in range(K):
    x, y = map(int, input().split(" "))
    visited[y][x] = 1

y가 앞에 들어가야지 y는 층수니깐 0 층에 0 / 0층에1 이런식으로 들어간다.

 

for a in range(N):
    for b in range(M):
        if visited[a][b] == 1:
            bfs(a,b)
            cnt += 1

M 가로, N은 세로 visited[a][b] 가 1 > 밟을수 있는 땅이면 bfs 출발하고

def bfs(a,b):
    Q = deque([(a,b)])
    visited[a][b] = 0 # 1을 0 으로 방문했음
    while Q:
        x,y = Q.popleft()
        for sx, sy in move:
            dx, dy = x + sx, y + sy
            if dx < 0 or dx >= N or dy < 0 or dy >= M:
                continue
            if visited[dx][dy] == 1:
                Q.append((dx,dy))
                visited[dx][dy] = 0

계속해오던거 이어서 밟을 수 있는땅 0 으로 다 만들어 줌