[백준][파이썬]1012번: 유기농 배추

문제 출처 : www.acmicpc.net/problem/1012

1012번: 유기농 배추

내 풀이

bfs 문제였다.

맵을 돌면서 1인지 아닌지 체크해준 후

1, 즉 배추일 경우 bfs를 돌리면서 방문 한 곳을 0으로 바꿔준다.

후에 bfs가 끝나면 answer 에 1을 더하면서 카운트해준다.

from collections import deque

t = int(input())
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs(a, b):
    larva = deque()
    larva.append((a, b))

    while larva:
        a, b = larva.popleft()

        field[a][b] = 0

        for i in range(4):
            nx, ny = a + move[i][0], b + move[i][1]
            if (0 <= nx <= n - 1) and (0 <= ny <= m - 1) and (field[nx][ny] == 1):
                field[nx][ny] = 0
                larva.append((nx, ny))
                
    return True
        
for i in range(t):
    answer = 0
      
    m, n, k = map(int, input().split())
    field = [[0] * m for _ in range(n)]
    
    for j in range(k):
        x, y = map(int, input().split())
        field[y][x] = 1
        
    for a in range(n):
        for b in range(m):
            if field[a][b] == 1:
                bfs(a, b)
                answer += 1
    print(answer)

보기에는 쉬워 보이는데 사실 시간초과 때문에 꽤나 애를 먹었다. 

이것저것 바꿔봤는데도 시간초과를 해결할 수 없어서 여러 고민을 했다.

결국 문제는 bfs가 돌아가는 방식에 있었다.

움직여서 밟게 되는 좌표를 즉시 방문했다고 처리를 해주어야 하는데 그렇지를 않고 후에 방문처리가 되도록 되어있다보니 중복해서 방문하게 되는 경우가 발생했던 것이다.

이를 해결하기 위해 field[nx][ny] = 0으로 즉시 방문처리로 바꾸어서 추가했더니 시간초과가 일어나지 않았다.