[파이썬] 백준 1012 : 유기농 배추 (실버2)

백준 1012 : 유기농 배추 (실버2)

 

1012번: 유기농 배추

---

문제

 

---

풀이

 

0. 방향성 생각

군집의 개수를 측정하는 문제이므로 DFS로 접근해야함을 알 수 있다.

밭의 크기가 크지는 않지만 재귀적으로 DFS를 구현하면 오류가 발생할 수 있으므로 재귀 리미트를 설정한다.

 

 

1. DFS 함수 정의

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):
    if x<0 or y<0 or x>=N or y>=M :
        return 0
    if land[x][y] == True :
        land[x][y] = False
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

 

2. 입력 받기

# 1)
T = int(input())
for t in range(T) :
    M,N,K = map(int,input().split())
    land = [[False]*M for i in range(N)]
    
    # 2)
    for i in range(K):
        x,y = map(int,sys.stdin.readline().split())
        land[y][x] = True
        
    # 3)
    count = 0
    for i in range(N):
        for j in range(M):
            if land[i][j] == True :
                dfs(i,j)
                count += 1
    print(count)

1) 테스트 케이스의 개수 T를 입력으로 받는다. for문 내부에서 밭의 크기와 배추의 개수를 받는다.

이후 테스트 케이스마다 사용할 2차원 리스트 land를 만든다.

 

2) 배추의 좌표를 입력받아서 land 정보를 업데이트 해준다.

 

3) 현재 테스트 케이스에서 군집의 개수를 셀 count 수를 정의한다.

배추를 찾으면 상하좌우로 연결된 배추가 모두 0으로 변한다. 이 때 군집의 크기를 하나 카운트 해준다.

 

---

전체 코드

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):
    if x<0 or y<0 or x>=N or y>=M :
        return 0
    if land[x][y] == True :
        land[x][y] = False
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1)
    return 0

T = int(input())
for t in range(T) :
    M,N,K = map(int,input().split())
    land = [[False]*M for i in range(N)]

    for i in range(K):
        x,y = map(int,sys.stdin.readline().split())
        land[y][x] = True

    count = 0
    for i in range(N):
        for j in range(M):
            if land[i][j] == True :
                dfs(i,j)
                count += 1
    print(count)