[백준_Python] 1012번 - 유기농배추 [실버 2]

황준성·2024년 11월 15일

BOJ_Python

목록 보기

13/70

문제

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

입력 예시 1

출력 예시 1

5
1

문제 이해

DFS 문제이다. 프로그래머스의 "네트워크", 백준의 "바이러스" 문제와 비슷하다. 그런데 시뮬레이션의 요소인 방향벡터를 곁들인, 그런 유형의 DFS문제이다.

문제에 대한 이해는 위의 설명으로 끝난다. 크게 설명할 부분이 없다. 상하좌우로 붙어있는 것을 하나로 간주하고 카운트하면 된다.

DFS문제를 풀면서 이해도를 높이고 있다보니 솔직히 크게 어렵진 않다. 실수로 두 값을 바꿔서 오류가 나는 정도이다. 처음에 백준을 처음 풀기 시작할때는 브론즈 1만 풀어도 힘들었는데, 알고리즘을 배우면서 문제에 익숙해지다보니 점점 문제의 킬각이 조금씩 보이기 시작한다. 예전에는 실버 4, 5 문제 풀기도 너무 힘들었어서 지금 실버 2를 어렵지 않게 푼다는게 신기하기 하다.

코드

# 백준 1012번 유기농 배추 DFS

# 백준에는 재귀깊이가 1000으로 제한되기 때문에 늘려준다 
import sys
sys.setrecursionlimit(10**6)

# 방향 벡터 동-서-남-북 순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def DFS(i, j):
    global graph
    graph[i][j] = False

    # 방향벡터로 4방향을 탐색
    for k in range(4):
        ny = i + dy[k]
        nx = j + dx[k]

        if 0 <= nx < M and 0 <= ny < N and graph[ny][nx]:
            DFS(ny, nx)



T = int(input())

for _ in range(T):
    # 0. 입력 및 초기화

    # 가로 M, 세로N, 배추 개수 K
    M, N, K = map(int, input().split())
    graph = [[False] * M for _ in range(N)]
    cnt = 0

    # 1. 그래프 연결 값 넣기
    for _ in range(K):
        x, y = map(int, input().split())
        graph[y][x] = True

    # 2. DFS 호출

    for i in range(N):
        for j in range(M):
            if graph[i][j] == True:
                DFS(i, j)
                cnt += 1
    
    # 3. 출력
    print(cnt)

이차원 리스트를 이중 반복문으로 돌면서 1인 경우에 DFS를 돌려주면 된다.

알아야할 스킬 or 정보

사실 이 문제한테 애를 먹었다. 쉽다고 해놓고 이게 무슨소리냐고 할 수 있지만 일단 진정하고 글을 읽어주기 바란다.

어제부터 풀었는데 계속 런타임에러가 나서 틀렸다. 근데 사실 "이걸" 알고있었다면 2번째 시도에 맞을 수 있었다. 첫번째 시도는 "런타임에러'(IndexError)'"이다. 이건 범위를 벗어났다는 의미다. 뭔가 로직에 이상이 있었다는 의미이다. 하지만 두번째 시도는 "런타임에러'(RecursionError)'"이다. 재귀함수는 영어로"recursive function"이다. 즉, Recursion은 "재귀"라는 뜻일거고, 재귀에 이상이 있다는 거다.