[python]1012_유기농 배추

사용한 자료구조 및 개념 : bfs, dictionary, set

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ 2차원 배열판을 만들 필요없이 배추 위치 입력값들로 바로 확인한다!

2️⃣ 배추 좌표를 키로하고 인덱스를 값으로 저장하는 딕셔너리를 만든다.

⇒ 지금 현재 배추 위치에서 상,하,좌,우에 해당 하는 값들의 인덱스를 빠르게 조회를 하기 위함이다.

✅ 딕셔너리는 해시 테이블을 기반으로 하므로 키를 사용한 값의 조회가 평균 O(1)의 시간 복잡도로 매우 빠르다. 이를 활용하면 특정 (x, y) 좌표가 존재하는지와 그에 해당하는 인덱스를 매우 빠르게 찾을 수 있다.

3️⃣ 배추 딕셔너리의 모든 키(배추 좌표)들을 가지고와 set으로 만든다.

⇒ 지금 현재 배추 위치에서 상,하,좌,우에 해당 하는 값들이 배추 리스트에 있었는지 빠르게 조회하기 위함이다.

✅ 집합은 멤버십 테스트(어떤 요소가 집합에 있는지 확인)를 O(1)의 평균 시간 복잡도로 수행할 수 있다. 이것은 리스트나 튜플과 같은 순차적인 자료구조보다 훨씬 빠르다. 따라서, 특정 (x, y) 좌표가 field_set에 있는지 확인하는 작업이 매우 빠르게 진행된다.

4️⃣ 인접한 배추들을 확인했는지 안했는지 판별하기 위한 리스트를 만든다.

5️⃣ 확인하지 않은 배추라면 상,하,좌,우 값을 계산해 배추 리스트에 있는지 확인한다.

6️⃣ 탐색(bfs)함수 cabbage가 종료되면 결과값을 +1 해준다.

 

---

Solution Code & 주석

from collections import deque

def cabbage(x, y):
    queue = deque([(x, y)])

    while queue:
        cur_x, cur_y = queue.popleft()
        for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dx = cur_x + i
            dy = cur_y + j
            if (dx, dy) in field_set and not check[field[(dx, dy)]]:
                check[field[(dx, dy)]] = True
                queue.append((dx, dy))

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    field = {tuple(map(int, input().split())): idx for idx in range(k)}
    field_set = set(field.keys())
    check = [False] * k
    res = 0

    for position, idx in field.items():
        if not check[idx]:
            cabbage(position[0], position[1])
            res += 1

    print(res)