[백준 1012] 유기농 배추

[BanApp]

pypy3

import sys
sys.setrecursionlimit(10000)
t = int(sys.stdin.readline())

def count(arr,i,j,tmp):
    arr[i][j] = '0'
    tmp.append(i)
    tmp.append(j)

    if arr[i + 1][j] == '1':
        if i + 1 >= 0 and j >= 0:
            count(arr, i + 1, j, tmp)

    if arr[i - 1][j] == '1':
        if i - 1 >= 0 and j >= 0:
            count(arr, i - 1, j, tmp)

    if arr[i][j + 1] == '1':
        if i >= 0 and j + 1 >= 0:
            count(arr, i, j + 1, tmp)

    if arr[i][j - 1] == '1':
        if i >= 0 and j - 1 >= 0:
            count(arr, i, j - 1, tmp)


for i in range(t):

    m, n, v = map(int, sys.stdin.readline().split())
 
    arr = []
    ans = []

    arr = list(['0'] * (m + 2) for _ in range(n + 2))

    for i in range(v):
        x = list(sys.stdin.readline().split())
        arr[int(x[1]) + 1][int(x[0]) + 1] = '1'

    tmp = []
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if arr[i][j] == '1':
                count(arr, i, j, tmp)
                ans.append(tmp)
                tmp = []

    print(len(ans))

DFS나 BFS로 푸는 문제지만 문제를 처음 봤을때 떠올랐던 아이디어가 있어서 한번 다른 방법으로 풀어봤다.
사실 DFS가 근본적으로 재귀구조라서 그것을 응용한것이라고 생각하면 된다.
기본적인 원리는 십자가 모양으로 동시에 탐색하는것이다.
[x+1, y], [x-1, y], [x, y+1], [x, y-1] 이런식으로 말이다.
이런 방식으로 재귀를 반복해서 1을 만나면 0으로 바꾼다.
그러다가 동서남북이 모두 0으로 둘러쌓이면 즉 주변에 더이상 1이 없으면 함수를 탈출하고 ans 배열에 tmp 배열이 들어간다.
글을 쓰다보니 느낀건데 tmp 배열을 쓰지않고 그냥 반복문안에 count변수를 써도 될것 같다.
결론적으로 위 과정을 반복하면 ans배열 안에 존재하는 원소들의 갯수가 필요한 벌레들의 마리수이다.
즉 ans안의 각 원소(tmp)에 들어있는 정수들은 벌레 한마리가 커버 할 수 있는 장소들의 위치 좌표인 것이다.

여기서 핵심 아이디어는 저 십자가 탐색법을 하면 문제가 생긴다. x가 0일때 [x-1]이 되면 인덱스가 음수가 되어 버린다.
파이썬에서는 try except를 사용해서 인덱스 에러를 피할 수 도 있지만 바람직한 방법이 아니다.
따라서 0으로 모든 리스트를 감싸주고 시작지점을 [1,1]로 지정해주면 인덱스 에러를 피할 수 있다.

작동속도 또한 생각보다 괜찮다. 위 알고리즘으로 백준에서 pypy3 사용자 중에서는 100등 정도에 랭크하고 있다.
위의 append를 리스트를 미리 초기화 시키고 '=' 을 사용하고 tmp 배열을 없애고 반복문 안에 count를 쓰면 시간복잡도 에서 더 유리할것 이라고 생각된다. 또한 파이썬은 기본적으로 재귀의 깊이가 제한되어 있으므로 sys 모듈에 있는 setrecursionlimit() 함수를 사용하는 것도 잊지 말자.

[ghdcksgml1]

잘푸셨네요!

# 함수 밖에
dx = [1,-1,0,0]
dy = [0,0,1,-1]

# count 함수 안에
for k in range(4):
    nx = i + dx[k]
    ny = j + dy[k]
    if arr[nx][ny] == '1':
        if nx >= 0 and ny >= 0:
            count(arr, nx, ny, tmp)

if 4개를 for문으로 묶어서 코드를 줄일수도 있을 것 같아요

[BanApp]

tmp 배열 버리고 count로 숫자세니깐 60등으로 올라갔음ㅋㅋㅋㅋ