[파이썬/python] 백준 - 20209 스트레이트 스위치 게임

문제

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

---

문제 설명

1. N개의 큐브, 그리고 일부 큐브와 연결되어 있는 K개의 스위치가 존재한다.
2. i번 스위치를 누르면 연결된 모든 큐브의 숫자가 각각 i 만큼 증가한다.
3. 큐브 위에는 0,1,2,3,4만 존재하며, 4를 초과할 경우 5로 나눈 나머지로 즉시 초기화된다.
4. 스위치를 한 번 누를 때, 반드시 단 한 개의 스위치만 누를 수 있다.
5. 같은 번호의 큐브가 한 스위치에 여러 번 연결되어 있는 경우는 없다.
6. 스위치를 누를 수 있는 횟수의 제한은 없다.
7. 큐브 위에 쓰여 있는 모든 숫자가 동일해지는 순간, 게임은 종료된다.
8. 눌러야 하는 스위치의 최소 횟수를 구한다. 

 

---

풀이

BFS를 통해서 문제를 해결했다.

 

이 문제의 핵심은 "주어진 값을 이용해서 어떻게 그래프로 변형할 것인가?"이다.

 

보통 그래프 문제들은 정점과 간선, 시작 정점이 주어진다.

그렇기에 탐색 알고리즘을 구현하고 값을 넣기만 하면 문제가 없었다.

 

하지만 이 문제는 다르다. 1번 예제를 통해서 알아보자.

4 2
0 1 0 1
2 1 3
3 1 2 3

큐브의 시작 모양은 [0, 1, 0, 1]이다. 이를 각 스위치를 통해서 변경할 것이다.

 

1번 스위치를 누르면 [1,1,1,1], 2번 스위치를 누르면 [2,3,2,1]이다. 

이를 그림으로 표현해 보면 위와 같은 그림이 나오게 될 것이다. 굉장히 익숙한 그림이다.

[0,1,0,1]은 시작 정점이고, 간선을 통해 각각의 새로운 정점이 생긴 것이다.

 

여기까지 이해했다면 BFS를 활용해서 문제를 풀 수 있다.

매 정점을 탐색하면서 새로운 간선, 정점들을 만들어내고 최솟값을 갱신하면 된다.

 

사실문제를 보자마자 BFS로 풀어야겠다고 생각했다.

이 문제는 정점이 주어지지 않아서 그래프 탐색인가?라는 생각을 쉽게 하지 못해서 아마 골드 3이라는 난이도를 매긴 것 같다.

 

하지만 이전에 비슷한 유형을 많이 풀어봐서 그런지 바로 생각이 나서 BFS 알고리즘을 사용했다.

그럼에도.. 50분 정도의 시간이 소요되었는데, 그 이유는...

바로 저 조건 때문이다..

저 조건을 제대로 안 읽어서 계속 +1을 했다. 분명 정답인 코드인데!! 자꾸 틀렸다고 나와서 시간을 너무 허비했다. ㅜ

 

문제 조건 하나하나 꼼꼼하게 보는 습관을 길러야겠다..

---

코드

import sys
from collections import deque
input = sys.stdin.readline

N,K = map(int,input().split())
startNode = ''.join(input().split())
switch = [list(map(int,input().split()))[1:] for _ in range(K)]

for i in range(N-1):
    if startNode[i] != startNode[i+1]:
        break
else:
    print(0)
    exit()

queue = deque([(startNode)])
visited = {startNode: 0}
def bfs():
    
    while queue:
        v1 = queue.popleft()
    
        for idx,s in enumerate(switch):
            tmp = list(map(int,v1))
            for i in s:
                tmp[i-1] = (tmp[i-1]+idx+1) % 5
            
            v2 = ''.join(list(map(str,tmp)))

            if v2 in visited:
                continue
            
            visited[v2] = visited[v1]+1
            queue.append(v2)

            for i in range(N-1):
                if tmp[i] != tmp[i+1]:
                    break
            else:
                return visited[v2]
        
    return -1

print(bfs())

---

시간복잡도

• BFS의 시간복잡도는 $O(V+E)$
• 나올 수 경우의 수는 각 큐브가 가지는 모든 숫자의 조합이므로 $5^8 = 4*10^5$이다.
•  따라서 약 $O(10^6)$ 정도(간선 포함)의 시간복잡도를 가진다고 보면 될 것 같다.