[백준] 1012번 유기농 배추 _ python

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

앞에서 푼 단지번호붙이기 2667번과 거의 유사한 느낌이다.
그런데도 꽤 오래걸렸다.
오래 걸린 이유는 input 받는 부분에서 막혔다.
1. 일단 어이없게도 가로 세로 길이로 m, n을 준다는 것에서 이걸 이중리스트로 구현할 때 row 개수가 m이 된다고 직관적으로 받아들이면 되는데, 가로 길이가 m이면 col 개수가 m이 된다고 착각..
2. 이중리스트 초기화 방법 오류

farm = [[0]*n]*m	# 1) 잘못된 방법
farm = [[0]*n for _ in range(m)]	# 2) 옳은 방법

잘못된 1번 방법으로 이중리스트를 초기화했더니
farm[a][b] = 1 이런 식으로 값을 할당하면
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
[[0, 2, 0, 0], [0, 2, 0 ,0], [0, 2, 0, 0]]
값이 이렇게 한꺼번에 바뀌는 이상한 현상이 나타난다.
리스트를 복사하기 때문에 나타나는 오류로 내부적으로 포함된 리스트가 모두 동일한 객체에 대한 레퍼런스로 인식되기 때문이라고 함.
반드시 2번 방법으로 초기화할 것..

풀이 방법은 재귀. 이중리스트 안에 1이 남아있으면 해당 인덱스로 타고 들어가서 상하좌우 계속해서 탐색하는 방법.

import sys
sys.setrecursionlimit(10000)

def count_warm():
    m, n, k = map(int, sys.stdin.readline().split())
    farm = [[0]*n for _ in range(m)]
    for i in range(k):
        a, b = map(int, sys.stdin.readline().split())
        farm[a][b] = 1

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

    def finding(x, y):
        farm[x][y] = 0
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or ny < 0 or nx >= m or ny >= n:
                continue
            elif farm[nx][ny] == 0:
                continue
            else:
                finding(nx, ny)

    for j in range(m):
        while 1 in farm[j]:
            l = farm[j].index(1)
            finding(j, l)
            result += 1

    return result

t = int(sys.stdin.readline())
for i in range(t):
    print(count_warm())