[백준][Python][1012][BFS] 유기농 배추

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

1012번: 유기농 배추

BFS 문제다.

 

맵에서 섬이 몇개냐, 단지가 몇개냐 하는 문제는 bfs로 풀 수 있는것 같다. 

왜 ~인 것 같다 면 난 이런 코딩테스트 문제들을 많이 안풀어봤고 실력도 솔직히 별로 없기 때문이다.

 

========이 아래로 뇌피셜========

이런 문제들은 bfs를 모든 맵에서 시작해보는 것으로 한다.

 

그리고 방문 확인용 배열 v를 만든다. 이 배열은 문제 내 모든 bfs 를 사용할때 공통적으로 사용된다.

그 후, deque를 통한 bfs를 돌리는데, v 를 통해 방문을 확인하고, 맵에서 (i,j) 지점이 섬/단지/배추 등등 우리가 필요한 곳인지 확인하는 작업이 필요하다. 아니면 continue를 통해 (i,j) 점에서 bfs는 돌리지 않는다.

그리고 탐색을 하고, 그 다음 단지갯수/섬갯수/배추 갯수 등등 (이 문제에서는 ret) 을 +1 해준다.

 

import sys
from collections import deque


t = int(input())

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


for _ in range(t):
    m, n, k = [int(i) for i in sys.stdin.readline().split()]

    d = [[0]*m for _ in range(n)]
    for _ in range(k):
        ax, ay = [int(i) for i in sys.stdin.readline().split()]
        d[ay][ax] = 1

    v = [[False]*m for _ in range(n)]

    ret = 0
    for i in range(n):
        for j in range(m):
            q = deque()
            if v[i][j] == True or d[i][j] == 0:
                continue

            v[i][j] = ret
            q.append((i, j))
            while q:
                y, x = q.popleft()
                v[y][x] = True
                for a in range(4):
                    cy, cx = y+dy[a], x+dx[a]
                    if 0 <= cy < n and 0 <= cx < m:
                        if v[cy][cx] == False and d[cy][cx] == 1:
                            q.append((cy, cx))
                            v[cy][cx] = True
            ret = ret + 1
    print(ret)