[백준 1012번] 유기농 배추 - 파이썬

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

1012번: 유기농 배추

 

 

💡문제 분석 요약

배추 밭에 배추가 심어진 부분과 심어지지 않은 부분이 있다. 배추가 심어진 부분은 연결되어 있으면 배추흰지렁이가 한마리만 있어도 된다. 배추흰지렁이는 총 몇마리가 필요한가?

 

💡알고리즘 설계

DFS를 이용하여 배추밭을 탐색하고, 더이상 배추가 없으면 배추흰지렁이의 개수를 추가한다.

 

1. 테스트 케이스의 개수를 입력받는다

2. 테스트 케이스만큼 배추밭의 크기와 배추의 개수를 입력받는다.

3. 배추밭을 한 행에서 한 칸씩 탐색하며, 그 칸에 배추가 있을 경우 주변 칸에도 배추가 있는지 탐색한다.

4. 주변 칸에도 배추가 있다면, 그 칸의 주변에 다시 배추가 있는지 탐색하고, 배추가 없다면 count에 1을 더한다.

5. 모든 칸을 탐색하면 배추흰지렁이의 개수를 출력한다.

 

💡코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

T=int(input())

def dfs(x, y):
    #동->남->서->북 순서
    dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]
    for dir_num in range(4):
        nx=x+dx[dir_num]
        ny=y+dy[dir_num]
        if 0<=nx<M and 0<=ny<N:
            if ground[ny][nx] == 1:
                ground[ny][nx] = 0
                dfs(nx, ny)

for _ in range(T):
    M, N, K=map(int, input().split())
    count=0
    ground = [[0 for _ in range(M)] for _ in range(N)]
    for _ in range(K):
        X, Y=map(int, input().split())
        ground[Y][X]=1
    for y in range(N):
        for x in range(M):
            if ground[y][x] == 1:
                dfs(x, y)
                count += 1
    print(count)

💡시간복잡도

O(NM)

 

💡 느낀점 or 기억할 정보

    dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]
    for dir_num in range(4):
        nx=x+dx[dir_num]
        ny=y+dy[dir_num]

 

격자 이동을 구현할 때 방향을 배열로 저장하면 쉽게 구현할 수 있다.

DFS 말고 BFS로도 풀어볼 수 있을 것 같다. BFS로도 풀어보고 싶다.