[DFS/BFS] 백준 #1012 유기농 배추 - Python

🗂️ 문제

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

 

 

💡 접근법

상하좌우로 인접해 있는 배추 무리의 개수를 구하는 문제이다. 따라서 너비 우선 탐색인 BFS를 사용하여 이를 계산하면 된다.

1. maps 리스트를 생성하고, 입력값으로 들어오는 배추의 위치에 값을 1로 둔다.
2. visited[] 리스트를 생성하여 방문한 위치에 대해서는 방문 처리를 해준다.
3. 모든 좌표를 순회하면서 1. 배추가 존재하면서 2. 방문하지 않은 조건에 해당하는 경우를 찾는다.
   만약 조건에 해당한다면, BFS()를 통해 인근 배추에 방문 처리를 한다. 이때 BFS()가 실행되는 수가 우리가 찾고자 하는 배추흰지렁이의 개수이다.
4. BFS()에서는 미리 선언해 둔 dx, dy 리스트를 통해 현재 위치에서 상하좌우에 대해 탐색한다.
   이때, if M > x > -1 and N > y > -1: 조건을 통해 좌표 범위를 벗어나지 않는지 확인해야 한다.
   만약, 탐색 위치에 배추가 존재하고, 처음 방문하는 것이라면 방문 처리 후 큐에 해당 위치를 삽입한다.

 

😎 내 코드

import sys
from collections import deque

def BFS(v):
    queue = deque([v])

    while queue:
        ay, ax = queue.popleft()
        
        for nx, ny in zip(dx, dy):
            x = ax + nx
            y = ay + ny
            if M > x > -1 and N > y > -1:
                if maps[y][x] == 1 and not visited[y][x]:
                    visited[y][x] = True
                    queue.append((y, x))

dx = [0, 0, -1, +1]  # 상하좌우
dy = [+1, -1, 0, 0]

T = int(sys.stdin.readline())

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())  # x, y, 개수

    maps = [[0] * M for _ in range(N)]
    visited = [[False] * M for _ in range(N)]

    for _ in range(K):
        a, b = map(int, sys.stdin.readline().split())  # (X, Y)
        maps[b][a] = 1

    cnt = 0
    for i in range(N):
        for j in range(M):
            if maps[i][j] == 1 and not visited[i][j]:
                cnt += 1
                visited[i][j] = True
                BFS((i, j))  # (y, x)

    print(cnt)

 

🧐 배운 점

가로길이 M(열)과 세로길이 N(행)이 일반 리스트에서 접근하는 방식과 다르기 때문에 이를 신경써서 처리해야 한다.

 

✅ 정답 확인