[백준] 1012번 유기농 배추 파이썬(Python) 풀이

1012번: 유기농 배추

[문제]

---

[코드]

#bfs 문제입니다

test = int(input())

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

def BFS(x,y):
    queue = [(x,y)]
    matrix[x][y] = 0 # 방문처리

    while queue:
        x,y = queue.pop(0)

        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 matrix[nx][ny] == 1 :
                queue.append((nx,ny))
                matrix[nx][ny] = 0 #방문처리



for i in range(test):
    M, N, K = map(int,input().split())
    matrix = [[0]*(N) for _ in range(M)]
    cnt = 0

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

    for a in range(M):
        for b in range(N):
            if matrix[a][b] == 1:
                BFS(a,b)
                cnt += 1

    print(cnt)

---

[해설]

BFS (너비 우선탐색)을 이용한 풀이 문제입니다

 

배추가 심어져 있는 경우 너비 우선 탐색 함수를 정의 해주고 이를 기반으로 주변 1칸씩 방문하여 1일 경우 0으로 처리해줍니다. 

그리고 cnt (카운트)를 하나씩 올려줍니다

 

이렇게 하면 최소값을 얻을 수 있습니다

 

#추가 코드 설명

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

 위 와 같은 리스트를 정의해준 이유 : 좌우, 위아래 한칸씩 이동하기 위해서

(-1,0) (1,0) (0,-1), (0,1)

 

            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue

전체 밭을 넘어갈때 무시하고 다음 순서로 넘어가기 위함

 

전형적인 BFS 문제입니다