BOJ1012 유기농 배추

Hoeun Lee·2021년 8월 18일
0
post-thumbnail

문제

BOJ1012 유기농 배추
실버II | 백준 1012 | Python3 파이썬 풀이


알고리즘

BFS 응용 문제이다. 원래는 분리집합(Union&Find)를 이용하는 문제인가 싶었는데, 단순한 탐색 문제였다.
백준의 그래프 탐색 활용 문제 중 가장 기본적인 구조이다.

방문하지 않는 배추에 대해 BFS 탐색을 실시하며 방문했다고 표시한다. 그 그룹의 개수(BFS를 탐색을 시작한 곳의 개수)가 정답이다.

원래는 방문 여부 배열을 따로 만들어서 하는 것이 정석이지만, 이 문제는 한 번 방문한 배추를 다시 방문할 필요가 없으므로 직접 배추밭 배열에서 탐색한 배추(1)를 지워(0으로 변경)버리는 방식으로 탐색했다.


코드

import sys
from collections import deque

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

def BFS(x, y):
    queue = list()
    queue.append([x, y])
    
    # BFS
    while queue:
        n, m = queue[0][0], queue[0][1]
        del queue[0]
        for ii in range(4):
        	# 상, 하, 좌, 우로 이동
            xx = n + move[ii][0]
            yy = m + move[ii][1]
			
            # 맵을 나가지 않고, 배추라면
            if 0 <= xx < N and 0 <= yy < M and table[xx][yy] == 1:
            	# 방문 체크
                table[xx][yy] = 0
                # 자식 노드 탐색
                queue.append([xx, yy])
            
            
T = int(sys.stdin.readline())

for t in range(T):
    N, M, K = map(int, sys.stdin.readline().split())
    table = [[0 for i in range(M)] for j in range(N)]
    count = 0
	
    # 배추밭
    for k in range(K):
        x, y = map(int, sys.stdin.readline().split())
        table[x][y] = 1
	
    # 모든 배추에 대해 탐색
    for x in range(N):
        for y in range(M):
            if table[x][y] == 1:
            	# BFS 탐색
                BFS(x, y)
                table[x][y] = 0
                # 그룹 개수 +1
                count += 1

    print(count)

결과

profile
건국대학교 컴퓨터공학부 이호은 | 알고리즘 정리 블로그

0개의 댓글