이번 문제는 BFS를 통해 해결하였다. 큐에 a, b, 지목 횟수를 넣어 BFS를 통해 탐색을 진행하였다. 중복을 제거하기 위해 visited 리스트를 2차원으로 선언하여 a, b를 짝지어 경우를 확인하도록 하였다. a먼저 지목시키고, 기존의 b와 비교한 후, 만약 같은 것이 있다면 결과 변수를 갱신하였고, b를 지목시켜 a와 비교한 후, 같은 것이 있다면 결과 변수를 갱신하였다. 이 둘 모두 만족하지 않고 통과한다면 2중 for문을 통해 a지목 2개와 b지목 2개의 경우를 모두 확인하며 중복 여부를 확인하고, 이를 통과하면 큐에 넣도록 하였다. while문이 종료되었을 때, 결과 변수가 초기값이라면 Evil Galazy를, 그렇지 않다면 결과 변수 값을 반환하도록 하였다.

Code

from collections import deque
n, a, b, da, db = map(int, input().split())
def hong_sam(a, b):
    q = deque()
    q.append((a-1, b-1, 0))
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[a-1][b-1] = True
    answer = 1e9
    while q:
        for _ in range(len(q)):
            ca, cb, cnt = q.popleft()
            nxt_a1, nxt_a2 = (ca+da)%n, (ca-da)%n
            cnt += 1
            if nxt_a1 == cb or nxt_a2 == cb:
                answer = min(answer, cnt)
                continue
            nxt_b1, nxt_b2 = (cb+db)%n, (cb-db)%n
            cnt += 1
            if nxt_b1 in (nxt_a1, nxt_a2) or nxt_b2 in (nxt_a1, nxt_a2):
                answer = min(answer, cnt)
                continue
            for nxt_a in [nxt_a1, nxt_a2]:
                for nxt_b in [nxt_b1, nxt_b2]:
                    if not visited[nxt_a][nxt_b]:
                        visited[nxt_a][nxt_b] = True
                        q.append((nxt_a, nxt_b, cnt))
    if answer == 1e9:
        return 'Evil Galazy'
    return answer
print(hong_sam(a, b))