백준 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)