[백준] 1012번 : 유기농 배추 (🥈실버 2) (Python)

문제 바로 가기

1012번: 유기농 배추

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2024-01-11

 

import sys
sys.setrecursionlimit(100000)

test_case_num = int(input())

drs = [0, 1, 0, -1]
dcs = [1, 0, -1, 0]

answer = 0
answers = []


def in_range(r, c):
    return r >= 0 and r < n and c >= 0 and c < m


def can_visit(r, c):
    if not in_range(r, c):
        return False
    if not grid[r][c]:
        return False
    if visited[r][c]:
        return False
    return True


def dfs(r, c):
    for dr, dc in zip(drs, dcs):
        nr, nc = r + dr, c + dc
        if can_visit(nr, nc):
            visited[nr][nc] = True
            dfs(nr, nc)


for _ in range(test_case_num):
    m, n, k = tuple(map(int, input().split()))

    grid = [
        [0] * m
        for _ in range(n)
    ]

    visited = [
        [False] * m
        for _ in range(n)
    ]

    for _ in range(k):
        c, r = tuple(map(int, input().split()))
        grid[r][c] = 1

    for i in range(n):
        for j in range(m):
            if grid[i][j] and not visited[i][j]:
                answer += 1
                dfs(i, j)

    answers.append(answer)
    answer = 0

for elem in answers:
    print(elem)

 

풀이 로직

• 그래프 탐색 방법 중 DFS으로 인접한 배추의 영역을 조사하면서 문제를 해결하였다.
• 이중 for문을 통해 2차원 밭을 탐색하고 배추가 심어진 곳을 발견하면, 해당 위치를 기점으로 주위 인접한 영역에 배추가 있는지 그래프 탐색을 통해 조사한다.
• DFS 탐색이 종료되면 해당 위치에서의 인접한 모든 배추는 조사되었음을 의미, 이중 for문을 통한 2차원 밭 탐색을 마저 진행한다.
• 2차원 밭 탐색이 모두 끝났을 때, 총 이뤄진 DFS 탐색 횟수가 우리가 구해야 할 배추흰지렁이의 수이다.
• 테스트 케이스가 총 T개이므로, 위의 로직을 T번만큼 반복하여야 한다. 따라서 미리 for문으로 감싸서 코드를 작성해야 하는 것도 짚고 가야 할 포인트이다.

 

문제 접근 과정 및 느낀점

• 코딩 테스트 준비를 하며 가장 열심히 연습했던 유형 중 하나라, 큰 어려움 없이 빠르게 문제를 해결할 수 있었다.
• 이번 문제에서 새롭게 알게 된 점이 있었는데, 파이썬에서 재귀 횟수의 제한을 직접 설정할 수 있다는 것이었다. 코딩 테스트에서 이 코드가 필요할 진 잘 모르겠지만, 혹시 모르니 알아두어야 겠다.

import sys
sys.setrecursionlimit(100000)