SWEA 10805 - 야바위 D-Ⅳ

이 문제는 SW Expert Academy 문제입니다.

SWEA 10805 - 야바위

문제

동호는 공과 N개의 컵을 가지고 야바위를 하고 있다.
N개의 컵은 모두 구별이 가능하고, 일렬로 늘어서 있다.
처음에 왼쪽에서 첫 번째 컵에 공을 넣어놓는다.
그리고 앞으로 Q번 두 컵의 위치를 바꾸는데, i번째에는 왼쪽에서 Ai번째 컵과 왼쪽에서 Bi번째 컵의 위치를 바꾼다.

동호는 공이 어떤 컵에 있는지 맞출 수 없도록 하기 위해 정확히 한 번 속임수를 쓰려고 한다.
속임수는 현재 공이 들어있는 컵이 왼쪽에서 i번째 컵이라고 할 때, 왼쪽에서 i-1번째 컵이나 왼쪽에서 i+1번째 컵으로 공을 순간 이동시키는 것이다.
이 속임수는 컵을 섞는 도중이 아니라면, 어떤 시점에도 가능하다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N,Q (1 ≤ N, Q ≤ 105)가 공백 하나로 구분되어 주어진다.

다음 Q개의 줄의 i번째 줄에는 두 정수 Ai,Bi (1 ≤ Ai, Bi ≤ N)가 공백 하나로 구분되어 주어진다.

출력

각 테스트 케이스마다 N개의 컵 중에 컵을 다 섞고 난 다음 공이 들어있을 수 있는 컵의 개수를 출력한다.

How to Solve?

처음에는 속임수 사용한 상태, 미사용한 상태로 나눈 배열을 이용해 DP를 이용하고자 했다.

✨ DP 로직
입력으로 주어진 N = 10, Q = 5, query = (1,7), (2,7), (1,9), (2,9), (4,6) 이라고 한다면 초기 상태는 아래와 같다.
0인 Init 상태로 맨왼쪽 컵에 공이 들어있는 위쪽 테이블과 시작하자마자 속임수를 사용한 아래 테이블 상태로 나눌 수 있다.

첫 번째 query = (1,7) 을 수행하게 되면 속임수를 사용하지 않은 상태인 왼쪽 테이블은 1번 row 상태로 1번과 7번의 위치가 바뀐 값이 된다.
속임수를 사용한 상태는 변화가 없다.

속임수 사용하지 않은 상태

속임수 사용한 상태

위 상태에서 속임수를 사용하지 않은 1번 row에서 속임수를 사용한 상태를 덮어씌워준다.
즉, 7번 컵에 들어있는 공이 6번, 8번으로 이동할 수 있다. 공이 있을 수 있는 모든 컵을 찾기 때문에 1로 만들어주면 된다.

속임수 사용하지 않은 상태

속임수 사용한 상태

다음 query (2, 7) 을 수행하게 되면 다음과 같다.

속임수 사용하지 않은 상태

속임수 사용한 상태

속임수를 사용한 상태에서의 공 섞는 과정은 2번의 공이 7번으로 옮겨가 6, 7, 8번 컵이 1이 되고,
속임수를 사용하지 않은 상태는 2번 컵에 있기 때문에 여기에서 속임수를 사용해 1번과 3번으로 이동가능하다.
위와 같은 과정을 (1, 9), (2, 9), (4, 6) 까지 모두 진행하게 되면 아래와 같은 상태가 된다.

속임수 사용하지 않은 상태

속임수 사용한 상태

무조건 속임수를 한 번 사용한다고 했으니 속임수 사용한 상태의 마지막 값의 합을 구하면 답이 나온다.

🔥 문제점!

입력이 N, Q = 100,000 이기 때문에 배열이 2 x 100,000 x 100,000 가 되면서 메모리 초과가 발생한다.
따라서 배열을 줄여줄 방법을 생각한다.

🔴 굳이 trick x query x cups 로 만들 필요가 없다. 결국 1인 위치들은 모두 고려해야하기 때문에 컵만 남겨둬도 충분히 모든 경우를 체크할 수 있다.

1. query 수행 - 간단히 컵에 들어있는 수를 바꿔주면 된다.

board[A], board[B] = board[B], board[A]

2. 속임수 사용 - 속임수를 사용하지 않은 상태에서의 공의 위치를 기억해두고 그 양 옆의 컵에 공을 추가로 넣어주면 된다.

board[ball_loc-1] = 1
board[ball_loc+1] = 1

if ball_loc == A:
    ball_loc = B
elif ball_loc ==B:
    ball_loc = A

🔥 주의할 점!

처음에는 공을 섞는 과정을 함수로 만들어 호출하고
A, B를 입력받을 때마다 위 과정을 수행하도록 만들었는데 이렇게 수행하면 시간초과가 발생한다.
query를 한번에 받고 for문으로 꺼내면서 query를 사용할 떄 map(int, query) 해야만 시간초과가 발생하지 않는다.

코드로 차이를 확인해보자.

## 쿼리를 받을때마다 로직을 수행하고 컵 섞는 과정을 함수로 호출하는 버전
for time in range(1, Q+1):
    A, B = map(int, input().split())
    # 1. 속임수 미사용한 상태 shake
    shake(0, time, A, B)
    if ball_loc == A or ball_loc ==B:
        ball_loc = B if ball_loc == A else A

    ## 2. 속임수 사용한 상태 shake
    shake(1, time, A, B)

    ## 3. 속임수 사용
    if 0 < ball_loc-1 <= N:
        board[1][time][ball_loc-1] = 1

    if 0< ball_loc+1 <= N:
        board[1][time][ball_loc+1] = 1
#######################################################################################

## 쿼리를 한번에 받았다가 하나씩 꺼내쓰는 버전
query = [list(map(int, input().split())) for _ in range(Q)]
for q in query:
    A, B = q
    ## 속임수 사용
    board[ball_loc-1] = 1
    board[ball_loc+1] = 1

    if ball_loc == A:
        ball_loc = B
    elif ball_loc ==B:
        ball_loc = A

    board[A], board[B] = board[B], board[A]

함수를 호출하는 연산이 추가되어 좀 더 오래걸린다고 하더라도 query를 한 번에 받아두고 처리하는 것과 받으면서 처리하는 작업의 차이는 이해가 가지 않는다. buffer로 인해 발생하는 것인지 잘 모르겠다.

최종 코드

✨ Python Code

T = int(input())
for t in range(1, T+1):
    N, Q = map(int, input().split())
    board = [0]*(N+2) ## 속임수 사용 여부 x col(컵 개수)

    ## 공의 위치
    ball_loc = 1
    query = [list(map(int, input().split())) for _ in range(Q)]
    for q in query:
        A, B = q
        ## 속임수 사용
        board[ball_loc-1] = 1
        board[ball_loc+1] = 1

        if ball_loc == A:
            ball_loc = B
        elif ball_loc ==B:
            ball_loc = A

        board[A], board[B] = board[B], board[A]



    board[ball_loc-1] = 1
    board[ball_loc+1] = 1
    print("#{} {}".format(t, sum(board[1:-1])))

문제 자체는 쉬운 편이었지만 입력을 처리하고 함수 호출, if문 개수 세세한 부분까지 신경써야만 통과하는 문제였다.

💥 끝!!

✨ 잘못된 부분은 많은 조언 및 지적 부탁드립니다. - JunHyxxn