유기농 배추 - 1012번

BFS로 해결하였다.

 

x, y로 나타낼 수 있는 문제의 어려웠던 점은 2중 배열로 표현을 하거나, 인덱스로 접근할 때, y와 x의 위치를 바꿔서 사용해줘야 한다는 점이다. 

가로 5칸, 세로 3칸을 x = 5, y = 3이라 할 수 있다.

이것을 우리가 익숙한 좌표평면행태로 보고 싶다면 arr[5][3] 이 아니라 arr[3][5]모양으로 만들어줘야한다. (파이썬에서는 이런방식으로 array를 표현하지 않지만 편의상 이렇게 적었다.)

arr[3][5]를 파이썬 식으로 표현하면 arr [ [ 0 ] * 5 for _ in range(3) ] 이고,

arr = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 로 보인다.

만약 이 배열에서 x = 2, y = 1 에 접근하고 싶다면

arr[2][1] 이 아니라 arr[1][2]로 접근해줘야 한다.

arr[2][1] = 1 을 하여 출력해보면 [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 1, 0, 0, 0]] 로 x = 1, y = 2 위치의 값이 변경된 것을 확인할 수 있다.

 

 

import sys
from collections import deque

direction = [[1,0],[-1,0],[0,1],[0,-1]]


t = int(input())

def bfs(x,y):
    visited[y][x] = True
    queue = deque([(x,y)])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            xx = direction[i][0] + x
            yy = direction[i][1] + y

            if 0 <= xx < m and 0 <= yy < n and field[yy][xx] == 1 and not visited[yy][xx]:
                queue.append((xx,yy))
                visited[yy][xx] = True


for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().split())
    visited = [[False]*51 for _ in range(51)]
    field = [[False]*51 for _ in range(51)]

    

    for _ in range(k):
        x, y = map(int,sys.stdin.readline().split())
        field[y][x] = 1
    ans = 0
    for i in range(n):
        for j in range(m):
            if field[i][j] == 1 and visited[i][j] == False:
                ans+=1
                bfs(j,i)
    print(ans)