[백준 2024/04/05] 1012번 유기농 배추

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

1012번: 유기농 배추

 

1. 접근 방법

이 문제는 '2667번 단지번호 붙이기'처럼 접근해서 재귀적으로 풀었더니 깊이 초과가 되어서, 다른 방식으로 접근했어야 했다.

우선 재귀적으로 접근하였던 코드는 다음과 같다.

def setting():
    m, n, k = map(int, input().split())
    list_r = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(k):
        x, y = map(int, input().split())
        list_r[y][x] = 1

    return list_r, m, n


def white(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return 0
    if list_r[x][y] == 0:
        return 0

    list_r[x][y] = 0
    return 1 + white(x - 1, y) + white(x + 1, y) + white(x, y + 1) + white(x, y - 1)


num = int(input())
for _ in range(num):
    list_r, m, n = setting()
    total = 0
    for i in range(n):
        for j in range(m):
            if list_r[i][j] == 1:
                white(i, j)
                total += 1

    print(total)

이렇게 구성하였지만, 깊이 초과 문제를 해결하기 위해서 다시 for 문을 이용해서 구성했었다.

 

def setting():
    m, n, k = map(int, input().split())
    list_r = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        list_r[y][x] = 1

    return list_r, m, n

def white(x, y, list_r, m, n):
    if x < 0 or x >= n or y < 0 or y >= m or list_r[x][y] == 0:
        return 0
    list_r[x][y] = 0

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for dx, dy in directions:
        white(x + dx, y + dy, list_r, m, n)
    return 1

num = int(input())
for _ in range(num):
    list_r, m, n = setting()
    total = 0
    for i in range(n):
        for j in range(m):
            if list_r[i][j] == 1:
                white(i, j, list_r, m, n)
                total += 1

    print(total)

하지만 이것도 깊이 초과 문제가 발생하였다.

이번 방법은 directions를 구성해놓고, for문으로 다시 white 함수에 접근하는 방식이었다.

사실상 생각해보면 위에서 재귀적으로 접근한 코드와 다를 바 없다고 생각한다.

 

따라서 다음으로 접근한 방식은 stack 방식이다.

먼저 특정 위치에 접근하게 되면 해당 위치를 stack에 넣고, 값을 0으로 바꾸어 준다.

 

이후 stack을 pop하고 해당 스택을 기준으로 위, 아래, 왼쪽, 오른쪽을 접근하여 기존에 충족된다면, 해당 값을 0으로 만들고 해당 위치를 다시 stack에 넣었다. 이를 stack 이 빌 때까지 즉, 주변에 1을 다 count할 때까지 접근하여 계산해 주었다.

 

따라서 해당 함수는 재귀적으로 구성되지 않고 문제를 해결할 수 있다.

 

2. 코드

def setting():
    m, n, k = map(int, input().split())
    list_r = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(k):
        x, y = map(int, input().split())
        list_r[y][x] = 1

    return list_r, m, n


def white(x, y):
    if list_r[x][y] == 0:
        return 0

    stack = [(x, y)]
    list_r[x][y] = 0

    while stack:
        cx, cy = stack.pop()

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < n and 0 <= ny < m and list_r[nx][ny] == 1:
                list_r[nx][ny] = 0
                stack.append((nx, ny))


num = int(input())
for _ in range(num):
    list_r, m, n = setting()
    total = 0
    for i in range(n):
        for j in range(m):
            if list_r[i][j] == 1:
                white(i, j)
                total += 1

    print(total)