[Algorithm] 백준 1012

문제

솔직히 문제가 뭐라고 하는지 정말 하나도 모르겠어서 그거 때매 헤맸다.
아니 나는 상하좌우 배추가 있어야지 지렁이를 심을 수 있다고 생각했는데,, 그게 아니더라
그냥 이어져있으면 배추를 심을 수 있다는 거였담.

풀이

내가 푼 알고리즘

이 코드는 배추밭의 상태를 입력받고, 인접한 배추뭉치들을 찾아내는 알고리즘입니다.

1. 입력:

   • 먼저, 배추밭의 크기를 나타내는 정수 n을 입력 받습니다.
   • 그런 다음, 배추밭의 크기 n과 배추의 개수 num, 그리고 각 배추의 위치를 입력 받습니다.

2. bfs 함수:

   • bfs 함수는 주어진 위치에서 시작하여 인접한 배추뭉치를 찾아내는 재귀적인 방식으로 동작합니다.
   • 현재 위치의 배추를 제거하고, 상하좌우에 인접한 위치에 배추가 있는지 확인하고, 있다면 그 위치에서 다시 bfs 함수를 호출합니다.

3. 주요 알고리즘:

   • 모든 배추의 위치를 순회하면서 bfs 함수를 호출하여 배추뭉치의 개수를 구합니다.
   • 이를 반복하여 배추밭 전체에 대해 배추뭉치의 개수를 구합니다.

4. 결과 출력:

   • 각 배추밭에 대해 구한 배추뭉치의 개수를 출력합니다.

이 알고리즘은 재귀적인 방식으로 동작하며, 모든 배추뭉치를 찾아내기 위해 인접한 위치를 탐색합니다.

시간 복잡도

• 이 알고리즘의 시간 복잡도는 O(n*m)입니다. 각 배추의 위치마다 bfs 함수를 호출하여 인접한 배추뭉치를 찾기 때문에, 모든 배추 위치에 대해 인접한 배추뭉치를 찾아야 합니다.

공간 복잡도

• 이 알고리즘의 공간 복잡도는 O(n*m)입니다. 배추밭의 크기에 비례하여, 배추의 위치를 저장하는 리스트인 cabbage_table의 크기가 결정되기 때문입니다.

코드

import sys
sys.setrecursionlimit(10**6) ### 재귀 깊이 한계 바꾸기

n = int(input())

for k in range(0, n):

    n, m, num = map(int, input().split(' '))

    cabbage_table = []

    for i in range(0, num):
        x, y = map(int, input().split(' '))
        cabbage_table.append([x, y])

    def bfs(x, y):
        cabbage_table.remove([x, y])
        a, b, c, d = [x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]
        if a in cabbage_table:
            bfs(a[0], a[1])
        if b in cabbage_table:
            bfs(b[0], b[1])
        if c in cabbage_table:
            bfs(c[0], c[1])
        if d in cabbage_table:
            bfs(d[0], d[1])

    cnt = 0
    while len(cabbage_table) != 0:
        cnt += 1
        x, y = cabbage_table[0][0], cabbage_table[0][1]
        bfs(x, y)
        
    print(cnt)

Lesson Learn

자료구조 복습하기

나는 구현하면서 리스트를 써야하는지 튜플을 써야하는지 암튼 자료구조 측면에서 뭐가 좋은지 고민이 많았다.
복습해야겠다..

이 경우에는 주어진 배추의 위치를 저장하는 자료구조로 리스트를 사용하는 것이 더 적합합니다. 이유는 다음과 같습니다:

1. 변경 가능성:

   • 주어진 문제에서는 주어진 배추의 위치를 탐색하면서 해당 위치를 제거해야 합니다. 이를 위해서는 변경 가능한(mutable) 자료구조가 필요합니다. 리스트는 변경 가능하므로 위치를 제거할 수 있습니다. 반면에 튜플은 변경 불가능한(immutable) 자료구조이므로 위치를 제거할 수 없습니다.

2. 탐색:

   • 주어진 배추의 위치를 탐색하면서 해당 위치를 제거해야 합니다. 리스트는 인덱싱과 삭제 연산을 지원하기 때문에 배추의 위치를 쉽게 탐색하고 제거할 수 있습니다.

따라서 이 경우에는 배추의 위치를 저장하는 자료구조로 리스트를 사용하는 것이 더 적합합니다.

Recursion Error, Name Error

import sys
sys.setrecursionlimit(10**6) ### 재귀 깊이 한계 바꾸기

이거 추가하니까 에러가 안났다. 뭐임.
Name Error 난 이유는 import sys 안해서 그랬다.