[Baekjoon 1012 / python / 실버2] 유기농 배추

문제

 

무난한 BFS 문제이다.

상하좌우로 연결된 영역이 몇개인지를 출력하면 된다.

 

# 실버2 -> BFS

"""

T : 테스트 케이스 개수

M : 열 ( 가로길이 )

N : 행 ( 세로길이 )

K : 심어진 배추 개수

table : 1은 배추, 2는 방문한 곳

"""

from collections import deque

import sys

input = sys.stdin.readline

T = int(input())

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

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

# 테이블 내에 있고, 배추인지 확인하는 함수

def going_no_going(nx, ny, table):

    if 0 <= nx < N and 0 <= ny < M and table[nx][ny] == 1:

        return True

    return False

# bfs 로직

def bfs(x, y):

    global table

    queue = deque()

    queue.append([x, y])

    table[x][y] = 2 # 방문 체크

   

    while queue:

        cx, cy = queue.popleft()

       

        for i in range(4):

            nx = cx + dx[i]

            ny = cy + dy[i]

            # 벌레의 전진

            if going_no_going(nx, ny, table):

                queue.append([nx, ny])

                table[nx][ny] = 2

for _ in range(T):

    M, N, K = map(int, input().split())

    table = [[0] * M for _ in range(N)]

    # 배추 위치 입력받기

    cabbage = []

    for _ in range(K):

        y, x = map(int, input().split()) # 입력값 행/열 반대라서 반대로 받는다

        table[x][y] = 1

        cabbage.append([x, y]) # 배추 위치 저장해두기

    # 모든 배추 위치 기준으로 BFS 진행

    result = 0

    for x, y in cabbage:

        if going_no_going(x, y, table):

            result += 1

            bfs(x, y)

    print(result)

 

deque을 사용한 BFS 로직을 활용했다.

 

방문 체크는 visited 테이블을 따로 만들지 않고 숫자를 2로 바꿈으로써 해결했다.

방문 가능한지 체크는 going_no_going 함수에서 -> 해당 좌표가 테이블 내에 있는가 + 방문하지 않은 배추(1)인가 로 확인했다. 

또한, 배추 위치를 미리 따로 저장해 두었다가 해당 위치에 한해서만 BFS를 진행했다.

BFS가 호출될 때 result를 추가했고, BFS 함수 내부에서는 방문 체크만 수행했다.

 

이 로직을 T번 반복해주면 된다.

 

결과