클라우드로 크고 싶은 블로그 입니다

백준 1012번: 유기농 배추 ( https://www.acmicpc.net/problem/1012 )

 

파이썬으로 풀이하다가 깨달은 사실이다.

 

먼저 아래와 같이 구현해 보았다.

def bfs(_x, _y):
    q = deque()
    q.append((_x, _y))

    while q:
        vx, vy = q.popleft()
        arr_map[vx][vy] = 0

        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = vx + dx, vy + dy
            if 0 <= nx < M and 0 <= ny < N and arr_map[nx][ny] == 1:
                q.append((nx, ny))

 

BFS 를 구현하기 위해

 

1. 최초 방문지를 큐에 추가

2. 큐에서 방문하지 않은 곳이 있다면, 큐에서 뺀다음 방문처리

3. 그리고 4방향 탐색

 

과 같이 구현하였다.

 

큐에서 빼면서 방문처리를 하니 계속 시간초과가 났다.

 

계속 보다 깨달았다.

 

BFS나 DFS 구현 시, 방문처리는 큐에서 뺄때가 아니라 큐에 넣을 때 해야된다는 사실을...

큐에 뺄 때 방문처리하면, 경우에 따라 큐에서 빼는 순서에 따라 이미 큐에 있는 곳을 다시한번 방문해서 큐에 넣는 경우가 발생하는 것을 알게 되었다.

 

BFS 함수를 아래와 같이 큐에 넣고 바로 방문 처리하는 것으로 수정 후 통과하였다.

def bfs(_x, _y):
    q = deque()
    q.append((_x, _y))
    arr_map[_x][_y] = 0

    while q:
        vx, vy = q.popleft()

        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = vx + dx, vy + dy
            if 0 <= nx < M and 0 <= ny < N and arr_map[nx][ny] == 1:
                q.append((nx, ny))
                arr_map[nx][ny] = 0

 

전체 적인 BFS 를 활용한 풀이는 아래와 같다.

 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(_x, _y):
    q = deque()
    q.append((_x, _y))
    arr_map[_x][_y] = 0

    while q:
        vx, vy = q.popleft()

        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = vx + dx, vy + dy
            if 0 <= nx < M and 0 <= ny < N and arr_map[nx][ny] == 1:
                q.append((nx, ny))
                arr_map[nx][ny] = 0

T = int(input())

for _ in range(T):
    M, N, K = map(int, input().split())
    arr_map = [[0] * N for _ in range(M)]
    ans = 0

    for _ in range(K):
        x, y = map(int, input().split())
        arr_map[x][y] = 1

    for x in range(M):
        for y in range(N):
            if arr_map[x][y] == 1:
                ans += 1
                bfs(x, y)

    print(ans)