이번 문제는 BFS를 통해 해결하였다. 처음에는 단순하게 생각하여 (n+1)*(n+1) 크기의 방문처리 리스트를 이용하여 구현하였다.

답은 잘 도출되었지만 n의 범위가 500,000까지였기 때문에 메모리 초과가 발생하였다. 그래서 이번에는 빈 리스트를 n+1개 가진 리스트로 방문처리를 진행하였다. 방문처리[a]에 b가 존재하는지를 확인하는 방식으로 구현하였는데, 이번에는 시간초과가 발생하였다.

다른 방법을 생각해보았고, 오리와 육리의 이동을 따로 처리하며, 다른 방문처리 리스트에 저장하기로 하였다. 이번에는 (n+1)*20 크기로 선언하였다. 20은 날짜의 수로, 19일을 넘어가면 오리와 육리는 더 이상 나아갈 수 없기 때문이다 (2^19 = 524288).

우선 오리의 이동을 BFS를 통해 구현하며 오리의 방문처리 리스트를 갱신해주고, 육리의 이동을 BFS를 통해 구현하며 육리의 방문처리 리스트를 갱신해주었다. 육리의 이동 시에는 매번 오리의 방문처리 리스트와 육리의 방문처리 리스트를 확인하여 값이 같을 경우가 있다면 바로 해당 값을 반환하도록 하였다.

Code

오답 코드 (메모리 초과)

from collections import deque
n, a, b = map(int, input().split())
da, db = [-1, 1], [1, -1]
def bfs(a, b):
    q = deque()
    q.append((a, b, 1))
    visited = [[False for _ in range(n+1)] for _ in range(n+1)]
    visited[a][b] = True
    while q:
        a, b, jump = q.popleft()
        if a == b:
            result = 0
            while jump > 1:
                jump //= 2
                result += 1
            return result
        for i in range(2):
            for j in range(2):
                na, nb = a+jump*da[i], b+jump*db[j]
                if 1 <= na <= n and 1 <= nb <= n and not visited[na][nb]:
                    visited[na][nb] = True
                    q.append((na, nb, jump*2))
    return -1
print(bfs(a, b))

오답 코드 (시간 초과)

from collections import deque
n, a, b = map(int, input().split())
da, db = [-1, 1], [1, -1]
a, b = min(a, b), max(a, b)
def bfs(a, b):
    q = deque()
    q.append((a, b, 1))
    visited = [[] for _ in range(n+1)]
    visited[a].append(b)
    while q:
        a, b, jump = q.popleft()
        if a == b:
            result = 0
            while jump > 1:
                jump //= 2
                result += 1
            return result
        if a > b:
            continue
        for i in range(2):
            for j in range(2):
                na, nb = a+jump*da[i], b+jump*db[j]
                if 1 <= na <= n and 1 <= nb <= n and nb not in set(visited[na]):
                    visited[na].append(nb)
                    q.append((na, nb, jump*2))
    return -1
print(bfs(a, b))

정답 코드

from collections import deque
n, a, b = map(int, input().split())
d = [1, -1]
a_visited = [[-1 for _ in range(20)] for _ in range(n+1)]
b_visited = [[-1 for _ in range(20)] for _ in range(n+1)]
def bfs_a(a):
    q = deque()
    q.append((a, 0))
    a_visited[a][0] = 0
    while q:
        cur, day = q.popleft()
        for i in range(2):
            nxt = cur+d[i]*(2**day)
            if 1 <= nxt <= n and a_visited[nxt][day+1] == -1:
                a_visited[nxt][day+1] = day+1
                q.append((nxt, day+1))
def bfs_b(b):
    q = deque()
    q.append((b, 0))
    b_visited[b][0] = 0
    while q:
        cur, day = q.popleft()
        if a_visited[cur][day] == b_visited[cur][day]:
            return day
        for i in range(2):
            nxt = cur+d[i]*(2**day)
            if 1 <= nxt <= n and b_visited[nxt][day+1] == -1:
                b_visited[nxt][day+1] = day+1
                q.append((nxt, day+1))
    return -1
bfs_a(a)
print(bfs_b(b))