🐨BOJ#1697 숨바꼭질]🙄BFS(feat. collections)

문제 보기

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

1697번: 숨바꼭질

풀이 아이디어

딱 봐도 dp로 풀 수 있을 것 같지만... 머리가 아파서(=어려워서)
수빈이가 도착할 수 있는 위치가 분기로 갈라지는 트리를 만들어서 풀기로 했다.

가장 적은 횟수(빠른 시간)에 동생을 찾아야 하기 때문에, 트리의 깊이가 가장 얕은 게 정답이다. 그래서 dfs로 탐색한 뒤 깊이를 비교하는 것 보다 bfs를 사용해야 한다고 생각했다.

그리고 분기를 하다보면 이미 나온 수가 나오기도 하기 때문에 visited를 체크해야 한다.

출력값은 트리의 깊이(?)다.

구현

큐 구현

큐를 빠르게 구현하기 위해 deque를 사용했다.
리스트에서 pop(0)을 사용하는 것과 collections.deque에서 popleft()을 사용하는 것은 성능에서 크게 차이가 있다.

먼저, 리스트는 동적 배열로 구현되어 있어서, 리스트의 시작 부분의 요소를 제거할 때 나머지 모든 요소를 한 칸씩 앞으로 이동시켜야 한다. 따라서 pop(0) 연산의 시간 복잡도는 평균적으로 O(N)이다.(N은 리스트 길이)

반면, collections.deque (덱, double-ended queue의 약어)은 양쪽 끝에서의 추가 및 제거가 매우 효율적이다.
덱은 이중 연결 리스트(이전 주소, 값, 다음 주소)로 구현되어 있어서, popleft() 연산으로 첫 번째 요소를 제거하는 것이 매우 빠르며, 이 연산의 시간 복잡도는 O(1)이다.

결론적으로, 많은 수의 요소를 다루는 상황에서 리스트의 시작 부분에서 요소를 자주 추가하거나 제거해야 한다면, collections.deque의 popleft() 메소드를 사용하는 것이 성능상 이점이 크다.

visited구현

구현을 위해 리스트를 쓰지 않고 defaultdict를 사용했다.
리스트와 collections.defaultdict 사이의 성능 차이는 주로 탐색 공간의 크기와 탐색 방식에 따라 달라진다.

리스트를 사용하는 경우:

• 장점: 인덱스 접근이 빠르므로, 특정 인덱스에 대한 방문 여부를 O(1) 시간 내에 확인
• 단점: 탐색 공간의 크기가 커지면 미리 큰 크기의 리스트를 할당해야 하며, 탐색 공간이 희소(sparse)할 경우 메모리 낭비가 심할 수 있다. 또한, 탐색 공간의 인덱스가 음수일 수 없으며, 비연속적이거나 큰 수의 인덱스를 다뤄야 하는 경우에는 적합하지 않다.

defaultdict를 사용하는 경우:

• 장점: 초기화할 필요 없이 필요한 키에 대해 자동으로 기본 값을 설정, 탐색 공간의 크기와 상관없이 사용
  탐색 공간이 희소할 때 효율적으로 메모리 사용. 인덱스나 키 값이 음수이거나 비연속적인 큰 수여도 문제 없음.
• 단점: 해시 테이블을 기반으로 하기 때문에, 리스트에 비해 특정 키에 대한 접근 시간이 약간 느릴 수 있다.(대부분 차이가 크지는 않다고 합니다.). defaultdict의 접근 시간 복잡도는 평균적으로 O(1)이지만, 최악의 경우(해시 충돌이 많을 때)에는 O(n)이 될 수 있다.

이 문제에서 방문할 수 있는 수는 0~100000인데 불연속적으로 방문하며, 실제 답을 찾기 위해 방문해야 하는 탐색 공간이 희소하다고 생각이 들어서 visited = [False]*100000 대신 defaultdict(bool)를 사용했다.

dict.get('key', False)를 쓸 수도 있다.

dict.get('key', False)

• 딕셔너리에서 키를 조회할 때 키가 존재하지 않으면 지정된 기본값(False 등)을 반환
• 키 조회는 일반적으로 O(1) 키가 존재하지 않는 경우에도 같은 O(1) 복잡도를 유지
• 키가 존재하지 않을 때 지정된 기본값을 새로 생성하지 않고, 단순히 지정된 기본값 반환

collections.defaultdict

• 기본값 생성 함수로 새 키에 대한 기본값을 자동으로 생성
• 키 조회 및 삽입 작업도 O(1)의 시간 복잡도
• 키가 존재하지 않을 때, 자동으로 기본값 생성. 딕셔너리에 추가.

성능 차이

• 메모리 사용 : defaultdict은 존재하지 않는 모든 키에 대해 실제로 기본값 객체를 생성하고 저장하므로, 이러한 키가 많을 경우 더 많은 메모리를 사용할 수 있습니다. 반면, dict.get()은 기본값을 반환하기만 할 뿐, 실제로 딕셔너리에 추가하지 않습니다.
• 속도 : 두 방법 모두 대부분의 경우에서 매우 비슷한 속도를 보입니다. 둘 다 키 접근은 O(1)의 시간 복잡도를 가집니다. 그러나 defaultdict는 존재하지 않는 키에 대해 기본값을 생성하고 딕셔너리에 추가하는 추가 작업이 필요하므로, 이러한 상황에서는 dict.get() 방식이 약간 더 빠를 수 있습니다.

결론: 결국 방문기록을 남기므로 여기선 차이가 없을 것 같다.

코드 보기 파이썬 BFS

from collections import defaultdict, deque

start, end = map(int, input().split())

# BFS
queue = deque()
queue.append((start, 0))  #숫자, 거리(연산 횟수) 저장
visited = defaultdict(bool) #기본값 false
visited[start] = True
while queue:
    v, count = queue.popleft()  # 숫자, 거리 추출
    if v == end:
        print(count)
        break
    for i in [v+1, v-1, v*2]:
        if 0 <= i <= 100000 and not visited[i]:
            queue.append((i, count+1))
            visited[i] = True

https://docs.python.org/ko/3/library/collections.html

collections — Container datatypes

collections 더 살펴보기

https://github.com/python/cpython/blob/3.12/Lib/collections/__init__.py

cpython/Lib/collections/__init__.py at 3.12 · python/cpython

---

이 모듈은 파이썬의 범용 내장 컨테이너 dict , list , set 및 tuple 에 대한 대안을 제공하는 특수 컨테이너 데이터형을 구현합니다.

namedtuple()	이름 붙은 필드를 갖는 튜플 서브 클래스를 만들기 위한 팩토리 함수
deque	양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
ChainMap	여러 매핑의 단일 뷰를 만드는 딕셔너리류 클래스
Counter	해셔블한 객체를 세기위한 딕셔너리 서브 클래스
OrderedDict	항목이 추가된 순서를 기억하는 딕셔너리 서브 클래스
defaultdict	누락된 값을 제공하기 위해 팩토리 함수를 호출하는 딕셔너리 서브 클래스
UserDict	더 쉬운 딕셔너리 서브 클래싱을 위해 딕셔너리 객체를 감싸는 래퍼
UserList	더 쉬운 리스트 서브 클래싱을 위해 리스트 객체를 감싸는 래퍼
UserString	더 쉬운 문자열 서브 클래싱을 위해 문자열 객체를 감싸는 래퍼

나는 Counter, deque, defaultdict이 가장 유용한 것 같다.

그리고 OrderedDict도 유용할 것 같다.