[백준] #1012(BFS)

DFS는 재귀를 사용하는데, 재귀를 사용하면 시간/메모리 초과가 나서 재귀 한도를 따로 설정해야 하기 때문에 그냥 BFS로 풀었다.

BFS는 너비 우선 탐색 알고리즘으로, 큐(queue)를 이용하는 알고리즘이다.

Python에서 큐를 사용하는 가장 효율적인 방법은 deque를 이용하는 것이기 때문에, 이를 이용하여 풀었다.

사실 직접 응용해보는건 아직 어려워서 다른 풀이의 접근방법을 찾아보며 코드를 작성했다. 혼자 뚝딱 푸는 날도 오것지?

from collections import deque

def bfs(x, y):
    q = deque()
    q.append((x, y))
    
    farm[x][y] = 0
    
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    while q: #큐가 빌 때까지 실행 (상하좌우가 모두 0인 점을 만날때까지)
        x, y = q.popleft()
    
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<N and 0<=ny<M and farm[nx][ny] == 1:
                farm[nx][ny] = 0 #1(배추)을 만나면 이미 방문했다고 표시 (새로 카운트할 필요 없음)
                q.append((nx, ny)) #배추의 상하좌우 다시 탐색

T = int(input())  
for _ in range(T):          
    M, N, K = map(int, input().split())
    farm = [[0]*M for _ in range(N)] #밭 초기화
        
    for _ in range(K):
        x, y = map(int, input().split())
        x, y = y, x
        farm[x][y] = 1 #배추 좌표 선입력
        
    cnt = 0

    for i in range(M):
        for j in range(N):
            if farm[j][i] == 1:
                bfs(j, i)
                cnt += 1 #한번도 방문하지 않은 곳 방문시 카운트 증가
                
    print(cnt)

🔍 코드 설명
1. 밭(farm)을 M*N 크기의 '0' 배열로 초기화한다.
2. 배추가 있는 곳의 좌표를 먼저 받아 1로 입력한다.
3. bfs함수: 입력받은 (x, y) 좌표의 상하좌우를 탐색, 즉 방문한다. 탐색하다가 1(배추)을 만나면 0으로 바꿔서 '이 좌표는 이미 방문했다'라고 처리한다.
4. 이제 farm 배열의 [0][0]부터 [N][M]까지 탐색, 1을 만나면(한번도 방문하지 않은 곳) 카운트를 증가시킨다.