[Python] 백준 풀기 1012 - 유기농 배추

파이썬 백준 1012번

실버2

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

1012번: 유기농 배추

 

 

 

 

 

문제 보기

분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

문제 풀기

이 문제를 DFS 로 풀기 위해서 sys.setrecursionlimit(10000) 모듈을 추가해야 한다. 파이썬 기본 재귀 한도는 1000 이기에 재귀 깊이가 1000을 넘어가게 되는 경우 런타임 오류가 발생한다.

 

주어진 배추의 위치를 matrix 2차원 리스트에 저장한다.

이때 문제에서 주어진 가로의 위치 m 과 세로의 위치 n 은 리스트에 입력될때 행과 열을 바꿔 입력하여 가로세로 2차원 리스트의 순서가 제대로 저장될 수 있도록 한다.

 

이제 모든 땅의 위치를 순차적으로 돌아보는데 첫 1이 나타나면 cnt += 1 를 해준다.

이제 1 이 나타난 순간부터 fnDFS 함수에 들어가 그 위치를 중심으로 좌, 우, 하, 상에 대해 1이 있는지를 보고 1이 있다면 그 위치를 의미 없는 숫자 7로 표시를 한다. 그리고 다시 또 fnDFS 함수로 들어가 중심 위치에서 좌, 우, 하, 상 탐색을 반복한다. 연결되어 있는 1이 모두 7로 표기될 때까지..

 

이렇게 모든 위치 탐색을 하고 나면 matrix 에 연결되었던 1들은 7로 바뀌어 있다. 홀로 떨어진 1의 경우 주변이 모두 0으로 둘러 쌓여 7이 되는 조건을 통과하지 못하여 그대로 있다. 그리고, 첫 1이 나타난 순간들만 카운트하여 누적된 cnt 값이 결과로 나오게 된다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
sys.setrecursionlimit(10000)

def fnDFS(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0 <= nx < M) and (0 <= ny < N):
            if matrix[ny][nx] == 1:
                matrix[ny][nx] = 7
                fnDFS(nx, ny)


if __name__ == "__main__":
    T = int(inputdata().strip())
    for _ in range(T):
        M, N, K = map(int, inputdata().split())
        matrix = [[0] * M for _ in range(N)]
        cnt = 0
        
        for _ in range(K):
            m, n = map(int, inputdata().split())
            matrix[n][m] = 1
        print(matrix)           # test print
            
        for i in range(M):
            for j in range(N):
                if matrix[j][i] == 1:
                    fnDFS(i, j)
                    cnt += 1
        print(matrix)           # test print
        
        print(cnt)



# 1
# 10 8 17
# 0 0
# 1 0
# 1 1
# 4 2
# 4 3
# 4 5
# 2 4
# 3 4
# 7 4
# 8 4
# 9 4
# 7 5
# 8 5
# 9 5
# 7 6
# 8 6
# 9 6


# [
#     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
#     [0, 0, 1, 1, 0, 0, 0, 1, 1, 1], 
#     [0, 0, 0, 0, 1, 0, 0, 1, 1, 1], 
#     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]

# [
#     [7, 7, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 7, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 7, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 7, 0, 0, 0, 0, 0], 
#     [0, 0, 7, 7, 0, 0, 0, 7, 7, 7], 
#     [0, 0, 0, 0, 1, 0, 0, 7, 7, 7], 
#     [0, 0, 0, 0, 0, 0, 0, 7, 7, 7], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]


# 5

 

 

 

 

 

추가 하기

예제 입력에 대한 출력

import sys
inputdata = sys.stdin.readline
sys.setrecursionlimit(10000)

def fnDFS(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0 <= nx < M) and (0 <= ny < N):
            if matrix[ny][nx] == 1:
                matrix[ny][nx] = 7
                fnDFS(nx, ny)


if __name__ == "__main__":
    T = int(inputdata().strip())
    for _ in range(T):
        M, N, K = map(int, inputdata().split())
        matrix = [[0] * M for _ in range(N)]
        cnt = 0
        
        for _ in range(K):
            m, n = map(int, inputdata().split())
            matrix[n][m] = 1
        print(matrix)           # test print
            
        for i in range(M):
            for j in range(N):
                if matrix[j][i] == 1:
                    fnDFS(i, j)
                    cnt += 1
        # print(matrix)           # test print
        
        print(cnt)



# 2
# 10 8 17
# 0 0
# 1 0
# 1 1
# 4 2
# 4 3
# 4 5
# 2 4
# 3 4
# 7 4
# 8 4
# 9 4
# 7 5
# 8 5
# 9 5
# 7 6
# 8 6
# 9 6
# 10 10 1
# 5 5


# [
#     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
#     [0, 0, 1, 1, 0, 0, 0, 1, 1, 1], 
#     [0, 0, 0, 0, 1, 0, 0, 1, 1, 1], 
#     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]


# 5



# [
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]


# 1







# 1
# 5 3 6
# 0 2
# 1 2
# 2 2
# 3 2
# 4 2
# 4 0


# [
#     [0, 0, 0, 0, 1], 
#     [0, 0, 0, 0, 0], 
#     [1, 1, 1, 1, 1]
# ]


# 2