[9/2] 유기농 배추

실버2 문제

내 코드

import sys
sys.setrecursionlimit(10000)

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())
    arr = [[0] * n for _ in range(m)]

    move_x = [1, -1, 0, 0]
    move_y = [0, 0, 1, -1]

    for _ in range(k):
        a, b = map(int, input().split())
        arr[a][b] = 1

    def dfs(x, y):
        arr[x][y] = 0
        for i in range(4):
            dx = x + move_x[i]
            dy = y + move_y[i]

            if (dx < 0 or dx >= m or dy < 0 or dy >= n ):
                continue
            if (arr[dx][dy] == 1):
                dfs(dx, dy)
        return True

    cnt = 0
    for i in range(m):
        for j in range(n):
            if (arr[i][j] == 1):
                cnt += 1
                dfs(i, j)

    print(cnt)

로직

• dfs 사용
• 재귀 에러가 떠서, sys.setrecursionlimit(10000) 를 사용했다.

다른 코드 (이코테 방식)

import sys
sys.setrecursionlimit(10000)

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())
    arr = [[0] * n for _ in range(m)]
    for _ in range(k):
        a, b = map(int, input().split())
        arr[a][b] = 1

    def dfs(x, y):
        
        if (x < 0 or x >= m or y < 0 or y >= n ):
            return False
        
        if (arr[x][y] == 1):
            arr[x][y] = 0
            
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)
            return True
        
        return False
        
    cnt = 0
    for i in range(m):
        for j in range(n):
            if (dfs(i, j) == True):
                cnt += 1
                
    print(cnt)

피드백

• 함수 4개를 사용했다.