[문제출처 : Codechef] 1부터 N까지의 N개의 숫자가 있습니다. 순서가 랜덤하게 배열되어 있다고 했을 때, 이를 permutation으로 봤을 때 생기는 cycles을 모두 출력하세요.
예를 들면, [2, 4, 5, 1, 7, 6, 3, 8]의 숫자 배열이 있다고 가정합시다. 그러면 처음에 2가 있기 때문에 두번째 숫자로 가고, 4가 나옵니다. 이제 4가 나왔기 때문에 다시 네번째 숫자로 가서 1을 발견합니다. 그럼 다시 첫번째로 가는데, 이는 이미 우리가 방문했던 숫자이기 때문에 [1, 2, 4, 1]이 cycle로 형성되게 됩니다.
다음번은 방문하지 않은 것 중 가장 먼저나오는 숫자, 즉 세번째 숫자부터 시작해서 또 같은 방법으로 cycle을 찾아나갑니다.
결국 [2, 4, 5, 1, 7, 6, 3, 8]는 4개의 cycles를 만들게 되고,
[1, 2, 4, 1]
[3, 5, 7, 3]
[6, 6]
[8, 8]
이렇게 4개를 출력하면 됩니다.
이 때, 이 문제를 푸는 방법은 여러 가지가 될 수 있겠지만, 이럴 때 가장 보편적으로 사용되는 방법은 element의 수만큼 boolean vector를 만들어서 방문 여부를 기록하는 방법입니다.
def permCycles(array):
#먼저 array 크기만큼 boolean vector(False로 초기화)를 만들어줍니다.
visited = [False]*len(array)
list_cycles = []
#첫번째 index부터 방문했는지 여부를 파악하면서 모두 방문할때까지 진행합니다.
for i in range(len(array)):
#해당 index가 방문했으면 continue
if visited[i]:
continue
#방문 안한 가장 빠른 index는 새로운 cycle을 형성합니다.
cycle = [i+1]
next_ind = i+1
while not visited[next_ind-1]:
visited[next_ind-1] = True #반드시 방문하면서 True로 바꿔줘야합니다!
next_ind = array[next_ind-1]
cycle.append(next_ind)
list_cycles.append(cycle)
return len(list_cycles), list_cycles
>>> print permCycles([2, 4, 5, 1, 7, 6, 3, 8])
(4, [[1, 2, 4, 1], [3, 5, 7, 3], [6, 6], [8, 8]])결과가 잘 나오네요 :) 이런 방법들이 결국엔 graph theory에도 많이 활용되니 잘 알아둡시다 :)