돌리기 ( 1682 번 )

1682번: 돌리기

 

---

🧠 알고리즘

• BFS (너비 우선 탐색, 완전 탐색 기반)

 

✔️ 동작 방식

• 초기 상태 (1,2,3,4,5,6,7,8) 을 시작점으로 큐에 넣고, 방문 집합(same_check)에 기록
• 매 단계마다 큐에서 하나의 상태를 꺼낸 뒤, 가능한 연산(A, B, C, D)을 적용하여 새로운 상태 생성
• 생성된 상태가 목표 상태 n과 동일하면 탐색 깊이(count)를 반환
• 이미 방문한 적 있는 상태는 큐에 넣지 않음 → 중복 탐색 방지
• 목표 상태를 찾을 때까지 BFS 진행

---

 

🧾 코드

import sys
from collections import deque

def _ch_q(now_q, now_type):
    if now_type == 'A':
        return (now_q[7], now_q[6], now_q[5], now_q[4], now_q[3], now_q[2], now_q[1], now_q[0])
    elif now_type == 'B':
        return (now_q[3], now_q[0], now_q[1], now_q[2], now_q[5], now_q[6], now_q[7], now_q[4])
    elif now_type == 'C':
        return (now_q[0], now_q[2], now_q[5], now_q[3], now_q[4], now_q[6], now_q[1], now_q[7])    
    elif now_type == 'D':
        return (now_q[4], now_q[1], now_q[2], now_q[3], now_q[0], now_q[5], now_q[6], now_q[7])


def _main(n):
    sq = (1, 2, 3, 4, 5, 6, 7, 8)
    queue = deque([(sq, 1)])
    same_check = {sq}

    if sq == n:
        return 0

    while queue:
        q, count = queue.popleft()
        for type in ('A', 'B', 'C', 'D'):
            new_q = _ch_q(q, type)

            if new_q == n:
                return count
                
            if new_q not in same_check: # 중복 체크
                queue.append((new_q, count + 1))
                same_check.add(new_q)
    

n = tuple(map(int, sys.stdin.readline().rstrip().split()))
print(_main(n))

---

 

 

⏱️ 시간 복잡도

while queue : 조건 만족시 까지 뎁스 반복
	for type in ('A', 'B', 'C', 'D') : 뎁스당 4개의 조건 처리
    
해당 알고리즘 시간 복잡도 ( 4^d개 )