1012-백준-유기농 배추

1. 문제 출처

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

1012번: 유기농 배추

2. 풀이

기초적인 BFS문제 이지만 , 가로 세로가 리스트에서는 [세로][가로]로 되어있어 헷갈렸었다... 조심하자.

from collections import deque
# 테스트 케이스 개수
t = int(input())
# 이동 경로(상하좌우)
dx = [0,0,-1,1]
dy = [-1,1,0,0]

for _ in range(t):
    # 팔요 벌레 개수
    worm = 0
    # 가로,세로,배추 개수 입력 받기
    m,n,k = map(int, input().split())
    # 밭 리스트
    farm = [[0]*m for _ in range(n)]
    # 방문 여부 리스트
    visted = [[0]*m for _ in range(n)]
    # 밭 리스트 초기화
    for idx in range(k):
        y,x = map(int, input().split())
        farm[x][y] = 1 
    
    for i in range(n):
        for j in range(m):
            # 만약 배추가 있고 방문하지 않은 지역이면
            # BFS를 통해 해당 배추와 인접한 배추를 전부 방문한다.
            if visted[i][j]  == 0 and farm[i][j] == 1:
                queue = deque([[i,j]])
                worm +=1
                # queue가 빌때까지
                while queue:
                    x,y = queue.popleft()
                    # 상하좌우 확인
                    for idx in range(4):
                        xx = x + dx[idx]
                        yy = y + dy[idx]
                        if 0<=xx<n and 0<=yy<m:
                            # 방문하지 않고 배추가 있는 지역이면 방문
                            if (visted[xx][yy] == 0) and (farm[xx][yy] > 0):
                                visted[xx][yy]  = 1
                                queue.append([xx,yy])
    print(worm)