[TIL 2024.07.23] 알고리즘 문제 풀이

오늘 진행한 일들

• 알고리즘 강의 시청
• 알고리즘 코드 문제 풀이

알고리즘 문제

유기농 농장(from 백준)

• 주어진 배추밭에서 인접한 배추 그룹을 찾아, 필요한 최소한의 배추흰지렁이 수를 계산
• 각 테스트 케이스에 대해 필요한 최소 배추흰지렁이 수 출력

라이브러리 임포트 및 입력 설정

import sys

input = sys.stdin.readline

이 코드는 sys 모듈을 사용하여 표준 입력으로부터 빠르게 데이터를 읽는다. sys.stdin.readline을 사용하면 많은 양의 데이터를 빠르게 처리할 수 있다.

방향 배열, 행과 열의 수 설정

def island_dfs_stack(grid, m, n):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = n, m  
    cnt = 0

가능한 이동 방향을 정의하기 위해 dx와 dy 배열을 사용한다. 이 배열들은 오른쪽, 왼쪽, 아래, 위로의 이동을 나타낸다.

그리드 순회 및 클러스터 탐색

for row in range(rows):
    for col in range(cols):
        if grid[row][col] != 1:
            continue

        cnt += 1
        stack = [(row, col)]

그리드의 각 셀을 순회하면서 값이 1인 셀을 발견하면 스택을 사용하여 DFS를 수행한다. 새로운 클러스터가 발견될 때마다 cnt를 증가시킨다.

스택을 사용한 DFS

        while stack:
            x, y = stack.pop()
            grid[x][y] = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 1:
                    continue
                stack.append((nx, ny))
return cnt

스택을 사용하여 현재 셀에서 시작하여 연결된 모든 셀을 방문한다. 방문한 셀은 0으로 설정하여 다시 방문하지 않도록 한다. 네 방향으로 이동하며 연결된 셀을 찾고 스택에 추가한다.

작성한 코드

import sys

input = sys.stdin.readline


def island_dfs_stack(grid, m, n):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = n, m  
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != 1:
                continue

            cnt += 1
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                grid[x][y] = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 1:
                        continue
                    stack.append((nx, ny))
    return cnt


t = int(input().strip())
for _ in range(t):
    m, n, k = map(int, input().strip().split())
    field = [[0 for _ in range(m)] for _ in range(n)]

    for _ in range(k):
        x, y = map(int, input().strip().split())
        field[y][x] = 1

    count = island_dfs_stack(field, m, n)
    print(count)