1012번: 유기농 배추 (python)

본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!!

 

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

1012번: 유기농 배추

 

기본 아이디어

• DFS를 활용
• 한 번 방문한 곳을 visited에다가 기록

 

import sys
sys.stdin = open('input_1012.txt', 'r')

sys.setrecursionlimit(10000)

def dfs(x, y):
    farm[y][x] = 1

    for d in range(4):
        new_x = x + dx[d]
        new_y = y + dy[d]
        if -1 < new_x < M and -1 < new_y < N and farm[new_y][new_x] and not visited[new_y][new_x]:
            visited[new_y][new_x] = 1
            dfs(new_x, new_y)

T = int(input())

for _ in range(T):
    M, N, K = map(int, input().split())

    farm = [[0 for _ in range(M)] for _ in range(N)]
    visited = [[0 for _ in range(M)] for _ in range(N)]
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    for _ in range(K):
        x, y = map(int, input().split())
        farm[y][x] = 1

    count = 0
    for j in range(N):
        for i in range(M):
            if not visited[j][i] and farm[j][i]:
                dfs(i, j)
                count += 1
    print(count)

 

유의사항

• 깊이 초과 때문에 sys.setrecursionlimit(10000)를 따로 지정해줬다.