[알고스팟/ALGOSPOT] 4. CLOCKSYNC

 

 

알고리즘 알고파! 알고라파덕

안녕하세요~ 알고라파덕입니다!

이번 문제는 CLOCKSYNC라는 문제인데요~

12시 3시 6시 9시로 되어있는 시계를 스위치를 이용해서 모두 12시로 바꾸는

최소로 눌러야할 스위치의 개수를 구하라 라는 것이에요.

모두 12시로 바꿀 수 없다면 -1을 출력해야 하구 시간초는 10S가 되겠어요~

 

먼저 이 문제의 올바른 풀이법은 BFS(너비우선탐색)라고 생각해요~ 흠 먼저 기존 상태에서

사용 할 수 있는 스위치를 판별을 하여 가지를 뻗어나가요. 가지를 뻗다 모두 12시가

되면 그 방법이 항상 최소 스위치 개수가 되기 때문에 그 수를 출력해요.

 

대략적인 그림을 그렸는데 저기 트리의 맨윗부분 기존에서 예를 들어 스위치를 5개 사용하였다면

다른 형태의 5개의 정보가 QUEUE 배열에 들어가게 되요. 또 다시 저 5개의 정보를 하나씩 사용 가능한

스위치를 사용하여 QUEUE 배열을 늘리는 거죠.

이런 방법은 BFS이지만.. 구현하기 쉽지는 않아요~ 매 순간의 정보를 같이 넣어주어야 하기 때문에 3차

원 배열을 이용하였습니다.

 

이 방법말고 다른 방법은 스위치들의 우선 순위를 정할 수 있어요

 

먼저 시계마다 사용할 수 있는 스위치 번호를 아래에 적으면 스위치가 1개인 것들이 있어요

시계당 스위치가 1개인 것은 그 스위치만으로 시계가 움직이기 때문에 다른 방법이 없는거죠.

그래서 먼저 우선순위에 둘 수 있어요. 처음에는 1번 4번 9번 스위치가 11 12 13에서 하나씩 밖에 없기

때문에 먼저 우선순위를 두고 저 1번 4번 9번을 사용해서 위에 적어논 스위치들 중에서 1번 4번 9번을

지웠을 때 다시 1개가 남는 10번이나 6번 등등 시계의 스위치를 마찬가지로 다음 우선순위에 둘 수

있어요. 이렇게 반복을 하다보면 확실한 우선순위를 알 수 있게 되고, 그 우선순위에 맞춰 시계를

직접 돌려주었을 때 모두 12시가 되면 그 개수를 출력하고, 아니면 -1을 출력하게 됩니다.

 

12시 3시 6시 9시를 십게 제어하는 방법은 입력을 받았을 때 X라고 한다면 X를 3으로 나누어주고

4로 모듈러 연산을 해줍니다. 그러면 12시는 0이 되고, 3시는 1, 6시는 2, 9시는 3으로 저장을 하고

스위치 개수를 계산할 때에는 4에서 0,1, 2, 3을 빼주고 4로 모듈러 연산을 한 것이 스위치를 돌려야 할

개수가 나옵니다. 예를 들어 6시인 경우에는 (4-2)%4 = 2가 되어 2번을 돌리면 12시가 될 수 있고,

12시인 경우에는 (4-0)%4 = 0이 되어 0, 3시인 경우에는 (4-1)%3 = 3이 되어 3번을 돌린다는 결과가

나와요. 쉽게 구현할 수 있습니당.

 

BFS 알고리즘은 알고리즘 설명이라는 카테고리에서 설명을 해드리겠습니다. 다른 적용하기 쉬운

문제들도 있어서 그 문제들과 BFS알고리즘 설명을 빠른 시일내에 올리겠습니다.

감사합니당~^0^

문제 출처 : https://algospot.com/judge/problem/read/CLOCKSYNC