BOJ(백준) 1012번 유기농 배추 파이썬

1012번: 유기농 배추

---

코드

import sys
r=sys.stdin.readline
T=int(r())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(T):
    M,N,K = map(int,r().split())
    field =[[0] * M for _ in range(N)]
    q = []
    worm = 0
    for _ in range(K):
        X,Y = map(int,r().split())
        field[Y][X] = 1
    for y in range(N):
        for x in range(M):
            if field[y][x]:
                q.append((x,y))
                worm += 1
                while q:
                    temp = q[0]
                    q = q[1:]
                    if field[temp[1]][temp[0]]:
                        field[temp[1]][temp[0]] = 0
                        for i in range(4):
                            new_x = temp[0] + dx[i]
                            new_y = temp[1] + dy[i]
                            if 0 <= new_x < M and 0 <= new_y < N and field[new_y][new_x]:
                                q.append((new_x,new_y))
    print(worm)

 

해설

[2667번] 단지번호붙이기 풀이 방법과 매우 동일하게 풀이하였다. 다만 입력을 받는 부분에서 차이고 있고 이번 문제에서는 방문여부를 확인할 check 2차원 배열을 따로 생성하지 않고 기존 field 2차원 배열내에서 방문한 지역을 1에서 0으로 변경하여 표시하였다.

 

결과