백준 1012 : 유기농 배추 파이썬 풀이(bfs 알고리즘)

 

 

백준 1012 번 유기농 배추문제입니다. 

 

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

1012번: 유기농 배추

 

입력은 첫 째줄은 테스트 케이스의 개수, 그 다음은  M, N, K 로 입력 받으며 가로길이 세로길이 배추의 개수입니다.

가로 길이가 M 세로 길이가 N 이라고 해서 헷갈렸는데 가로의 개수가 M개로 생각하면 됩니다. 

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

 

출력

5
1

 

deque() 를 사용했고 상하좌우를 확인하며 주변에 1이 있는지 확인하는 방법입니다.

배추 뭉텅이가 있는 곳이 끝나면 한 번의 bfs() 함수는 끝나게 되고 또 반복됩니다. 반복된 개수를 cnt 변수에 넣어주었습니다. 

from collections import deque

n = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#bfs로 해결
def bfs(graph, x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

for i in range(n):
    result = []
    cnt = 0
    m, n, k = map(int, input().split())
    #행렬 만들기
    li = [[0] * n for i in range(m)]
    for j in range(k):
        x, y = map(int, input().split())
        li[x][y] = 1
    for j in range(m):
        for z in range(n):
            if li[j][z] == 1:
                bfs(li, j, z)
                cnt += 1
    print(cnt)

 

 

 

 

 

 

 

이 문제는 바이러스 문제 풀이와 매우 유사했습니다.

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

2606번: 바이러스

바이러스 문제를 풀이한 글입니다. 

https://p-kyung.tistory.com/46

백준 2606번 : 바이러스 python 문제 풀이 (bfs 알고리즘)