[Python] 백준 1012번 유기농 배추

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

1012번: 유기농 배추

| 문제 내용

 

| 풀이

 

인접한 위치를 탐색해야 하는 문제라서 BFS 알고리즘을 사용했다.

처음에는 시간 초과 문제가 있었는데, 

첫 번째 원인은 큐에서 데이터를 추출할 때만 방문 여부를 확인했던 것이다. 이로 인해 아직 방문하진 않았지만 이미 큐에 추가된 위치 값들이 중복으로 들어가는 문제가 있었다. 따라서 큐에 위치 값을 추가할 때 방문 체크를 해주어야 중복 확인없이 탐색할 수 있다.

두 번째 원인은 값이 1인 배추들을 찾는 과정을 BFS 내에서 여러 번 반복했던 것이다. BFS 내에 작성 시 탐색을 완료한 후에 배열의 처음 위치부터 다시 탐색해야 하므로, BFS 함수 밖에서 체크를 해야 한다. 

 

import sys
input = sys.stdin.readline

def put_cabbage(ground, K):
    for _ in range(K):
        m, n = map(int, input().split())
        ground[n][m] = 1

def find_bug_by_bfs(i, j):
    queue = [(i, j)]
    # 현재 위치로부터 동서남북으로 위치한 인접 좌표 확인
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.pop(0)
        ground[x][y] = 2 # 배추가 없으면 0, 있으면 1, 방문한 곳이면 2

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 바운더리 안에 있고 확인하지 않은 배추인지 체크
            if (0 <= nx <= N - 1 and 0 <= ny <= M - 1) and ground[nx][ny] == 1:
                ground[nx][ny] = 2 # 큐에 넣을 때 방문 처리해서 중복 추가 방지
                queue.append((nx, ny))

T = int(input())
for i in range(T):
    cnt = 0
    M, N, K = map(int, input().split())
    # 2차원 배열 만들기
    ground = [[0 for _ in range(M)] for _ in range(N)]
    # 배추 위치한 곳 값은 1로 변경
    put_cabbage(ground, K)
    # BFS로 인접 배추들 확인
    for i in range(N):
        for j in range(M):
            if ground[i][j] == 1:
                find_bug_by_bfs(i, j)
                cnt += 1
    # 답 출력
    print(cnt)