1012

날짜 : 2022. 10. 30

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

def bfs(a, b):
    cabbage.append([a, b])
    field[a][b] = False
    # 이동
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    while cabbage:
        temp = cabbage.popleft()
        for i in range(4):
            x = temp[0] + dx[i]
            y = temp[1] + dy[i]
            if 0 <= x < m and 0 <= y < n and field[x][y] == True: # 범위에 있는 경우
                field[x][y] = False
                cabbage.append([x, y])
                continue
    return

t = int(sys.stdin.readline())  # 테스트케이스
cabbage = deque()  # 배추

for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().split())  # 가로, 세로, 배추 심긴 위치 개수
    field = [[False] * n for i in range(m)]
    cnt = 0
    for i in range(k):
        a, b = map(int, sys.stdin.readline().split())  # 심긴 위치
        field[a][b] = True
    #print(field) # 디버그
    for i in range(m):
        for j in range(n):
            if field[i][j] :
                cnt += 1
                bfs(i, j)
    print(cnt)

 

 

알게된 점

- BFS를 활용한 문제였다.

- 이전에 풀어본 아파트 단지 문제와 상당히 비슷한 유형이라 수월하게 풀 수 있었다.

 

 

참고 사이트

-