[백준 - Python] 1012. 유기농 배추 (DFS/BFS)

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

1012번: 유기농 배추

 

코드

from collections import deque

t = int(input())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque([(x, y)])
    mat[x][y] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue

            if mat[nx][ny] == 1:  # 방문하지 않은 노드인 경우
                queue.append((nx,ny))
                mat[nx][ny] = 0  # 방문 처리

for i in range(t):
    m, n, k = map(int, input().split())  # 배추밭 가로 길이 : m, 세로 길이 : n
    mat = [[0 for _ in range(n)] for _ in range(m)]
    cnt = 0

    for j in range(k):
        x, y = map(int, input().split())
        mat[x][y] = 1

    for a in range(m):
        for b in range(n):
            if mat[a][b] == 1:
                bfs(a, b)
                cnt += 1

    print(cnt)

 

서로 인접해 있는 배추들이 몇 군데 퍼져 있는지 조사하여,

총 몇 마리의 지렁이가 필요한지 파악하는 문제였다.

 

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해 있는 것이다.

 

2차원 행렬을 다룰 때,

행렬을 생성할 때와 인덱스를 다룰 때 헷갈리지 않게 주의해야 한다.

(사실 아직도 좀 헷갈림;;)

 

2차원 행렬을 다루는 나만의 풀이 법을 정해두고,

그 방식으로 연습하여 헷갈리지 않고 2차원 행렬을 빠르게 다룰 수 있게 연습해야겠다.

 

인접한 방향이 상하좌우 네 방향이기 때문에

방향 이동을 의미하는 dx, dy 리스트를 생성해 범위 4의 반복문으로 돌려서 확인을 하였다.

이 때, 해당 반복문 안에서 테두리 범위를 벗어나는지 확인해 주어야 한다.