5829번: Luxury River Cruise

www.acmicpc.net/problem/5829

5829번: Luxury River Cruise

아이디어:

해석부터 아주 어려웠던 문제..

그러니까 밑에 L,R로 주어진 M개의 문자열만큼을 K번 반복했을 때 어디에 위치하고 있는가를 구하는 문제이다.

M개의 이동을 반복하면 되니까 연산을 줄이기 위해 각 port 위치에서 M번 이동을 한 후의 위치를 다음 위치로 하는 새로운 그래프를 만들 수 있다. (cycle[port] = M번 이동한 후 위치)

그리고 K가 너무 크니까 이걸 줄여줘야 하는데 문제에서 사이클이 있다는 걸 알 수 있고, 사이클이 있다면 그 크기는 최대 N이므로 시간제한 안에 풀 수 있다.

사이클은 cycle[]을 1부터 돌면서 방문했던 곳에 다시 방문하면 종료 한다.

그런데 이때 cycle이 1부터 시작하지 않고 중간부터 시작해서 뱅뱅돌수도 있기 때문에 사이클의 길이를 다시 구해야 한다. 이 부분에서 내가 틀렸었는데.. 바보같이 length-(start-i)를 하면 되겠다라고 생각했다.. 노드의 크기는 순서와 맞지 않을 수도 있는데ㅠㅠ

아무튼 이렇게 사이클의 진짜 길이를 구하면, K%=length를 하여 계산하면 된다.

 

문제 너무 어렵다..ㅠㅠ

import sys

N,M,K = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
cycle = [0]*(N+1)
for i in range(1,N+1):
    left, right = map(int, sys.stdin.readline().split())
    graph[i] =[left, right]
choice = list(sys.stdin.readline().split())

#각 정점에서 M번 이동한 후 결과 새롭게 저장
for i in range(1, N+1):
    n = i
    for s in choice:
        if (s=="L"): n = graph[n][0]
        else: n = graph[n][1]
    cycle[i] = n
    
#사이클 찾기
visit = [False]*(N+1)
start = 1
length = 0 #주기 길이
while (True):
    if (visit[start]==True): #한번 방문한 노드를 다시 받문하면 사이클
        break
    visit[start] = True
    start = cycle[start]
    length+=1

#사이클이 시작하는 곳까지의 거리를 사이클 길이에서 빼줘야 함
cur = 1
for i in range(N+1):
    if (start==cur):
        length -= i
        break
    cur = cycle[cur]
    K-=1
    if (K==0): break #K가 사이클의 길이보다 작을때


if (K==0):
    print(cur)
else:
    K%=length
    for _ in range(K):
        cur = cycle[cur]
    print(cur)

 

그리고 이건 혹시 모를 테스트 케이스.. 구글링으로 구했다..ㅎㅎ

 

Input:

50 10 10
6 4
42 48
2 41
40 8
17 29
28 7
34 46
4 9
36 27
9 37
28 32
22 10
30 48
16 31
11 33
36 3
14 39
45 5
46 13
34 23
29 6
3 38
44 30
21 15
41 50
12 9
30 24
45 6
19 39
11 14
2 46
39 22
14 9
48 43
16 50
30 9
32 2
25 24
3 38
11 24
25 3
4 19
9 22
10 19
37 13
14 25
36 29
33 34
21 48
33 2
L L R L L R R R R R

 

Output:

50