[ 문제 ]

https://www.acmicpc.net/problem/9019

[ 알고리즘 유형 ]

그래프 이론
그래프 탐색
너비 우선 탐색

[ 정답 코드 ]

BFS

from collections import deque
import sys
MAX = 10001
sys.setrecursionlimit(MAX)
input = lambda : sys.stdin.readline()

def via_print(n, m):
    if n == m:
        return
    via_print(n, via[m])
    print(how[m], end='')

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        visited = [False] * MAX  # 방문여부 체크
        dist = [-1] * MAX  # 최단거리 기록
        via = [-1] * MAX  # 어디서 어디로 이동했는지 기록
        how = [''] * MAX # DSLR 중 어떤 방법으로 이동했는지 기록
            
        q = deque([n])
        dist[n] = 0
        visited[n] = True
        via[n] = -1
        while q:
            now = q.popleft()
            for index, nxt in enumerate([(now * 2) % 10000, now - 1, (now % 1000) * 10 + (now // 1000), (now % 10) * 1000 + (now // 10)]):
                if nxt == -1: nxt = 9999
                if not visited[nxt]:
                    q.append(nxt)
                    dist[nxt] = dist[now] + 1
                    visited[nxt] = True
                    via[nxt] = now
                    if index == 0: how[nxt] = 'D'
                    elif index == 1: how[nxt] = 'S'
                    elif index == 2: how[nxt] = 'L'
                    elif index == 3: how[nxt] = 'R'

        via_print(n,m)
        print()

[ 풀이 방법 ]

A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램을 작성하면 된다.
[step1] 최소로 문제를 해결하기 위해 BFS를 사용했다.
1) visited 리스트로 방문체크
2) dist 리스트로 최단거리를 기록

[step2] 어떤 명령어를 사용하였는지 기록하기 위해
1) via 리스트로 어디서 어디로 방문했는지 기록
2) how 리스트로 어떤 명령어를 사용했는지 기록

[step3] 그리고 어떻게 연산할지는 아래와 같이 구현하면 된다.

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

D: nxt = (n2)%10000
S: nxt = (n-1) if n-1 == -1 :v nxt = 9999
L: nxt = (n%1000)10 + (n//1000)
R: nxy = (n%10)*1000 + (n//10)

[step4] 출력
어떤 연산을 사용했는지 기록한 how를 출력하기 위해 via_print함수를 구현했다.

def via_print(n, m):
    if n == m:
        return
    via_print(n, via[m])
    print(how[m], end='')

[ 풀이과정 이슈 ]

1. 시간초과.. 하하하핳ㅎ핳하

from collections import deque
import sys
MAX = 10001
sys.setrecursionlimit(MAX)
input = lambda : sys.stdin.readline()

def via_print(n, m):
    if n == m:
        return
    via_print(n, via[m])
    print(how[m], end='')

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        dist = [[-1] for _ in range(MAX)]  # 최단거리 기록
        visited = [False] * MAX  # 방문여부 체크
        via = [[-1] for _ in range(MAX)]  # 어디서 어디로 이동했는지 기록
        how = [[''] for _ in range(MAX)]  # DSLR 중 어떤 방법으로 이동했는지 기록
            
        q = deque([n])
        dist[n] = 0
        visited[n] = True
        via[n] = -1
        while q:
            now = q.popleft()
            # D: nxt = (n*2)%10000
            # S: nxt = (n-1) if n-1 == -1 :v nxt = 9999
            # L: nxt = (n%1000)*10 + (n//1000)
            # R: nxy = (n%10)*1000 + (n//10)
            for index, nxt in enumerate([(now * 2) % 10000, now - 1, (now % 1000) * 10 + (now // 1000), (now % 10) * 1000 + (now // 10)]):
                if nxt == -1: nxt = 9999
                if not visited[nxt]:
                    q.append(nxt)
                    dist[nxt] = dist[now] + 1
                    visited[nxt] = True
                    via[nxt] = now
                    if index == 0: how[nxt] = 'D'
                    elif index == 1: how[nxt] = 'S'
                    elif index == 2: how[nxt] = 'L'
                    elif index == 3: how[nxt] = 'R'

        via_print(n,m)
        print()

해결

	visited = [False] * MAX  # 방문여부 체크
	dist = [[-1] for _ in range(MAX)]  # 최단거리 기록
        via = [[-1] for _ in range(MAX)]  # 어디서 어디로 이동했는지 기록
        how = [[''] for _ in range(MAX)]  # DSLR 중 어떤 방법으로 이동했는지 기록
            

=>

	visited = [False] * MAX  # 방문여부 체크
        dist = [-1] * MAX  # 최단거리 기록
        via = [-1] * MAX  # 어디서 어디로 이동했는지 기록
        how = [''] * MAX # DSLR 중 어떤 방법으로 이동했는지 기록
            

오... 리스트 초기화하는 과정에서 시간초과가 발생했다.
일차원 리스트로 MAX크기만큼 모든 값을 -1로 초기화를 하려했다.
그런데 실수로 [[-1] for _ in range(MAX)] 해당 방법으로 초기화를 했다. 즉, 이차원리스트로 초기화를 했던 것이다,,,
list comprehension 문법을 사용해 깊은 복사를 진행함과 동시에 쓸데없이 2차원리스트로 값을 초기화해 시간초과가 발생했다.

그래서
[-1] * MAX 얕은 복사임과 동시에 일차원 리스트 초기화인 해당 방법으로 수정했더니 시간초과 문제를 해결할 수 있었다.

그동안 입출력은 이제 잘 한다 생각하였지만 그렇지 않다는 생각이 들었고 이참에 입출력에 대해 다시 공부하고 정리하려한다.

1차원 리스트 초기화

방법1)

a = [-1] * MAX

방법2)

a = [-1 for _ in range(MAX)]

2차원 리스트 초기화

a = [[-1 for _ in range(MAX)] for _ in range(MAX)]

주의!!!
2차원 리스트 초기화할 때는
a = ([-1]5)5 와 같은 방법은 사용하면 안된다.
각 인스턴스마다 같은 주소값을 가져 값을 변경할 때 원하지 않던 값도 변경될 수 있기 때문이다.

ex)

a = [[-1]MAX]MAX

MAX = 3
a = [[-1]*MAX]*MAX
print(a)
for i in range(MAX):
    print(id(a[i]))
a[0][1] = 9
print(a)

👉 출력

[[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
2762149421704
2762149421704
2762149421704
[[-1, 9, -1], [-1, 9, -1], [-1, 9, -1]]

그렇다면 깊은 복사를 하는 list comprehension을 사용하면 어떨까?

a = [[-1 for _ in range(MAX)] for _ in range(MAX)]

MAX = 3
a = [[-1 for _ in range(MAX)] for _ in range(MAX)]
print(a)
for i in range(MAX):
    print(id(a[i]))
a[0][1] = 9
print(a)

👉 출력

[[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
2362958832264
2362991221640
2362991181576
[[-1, 9, -1], [-1, -1, -1], [-1, -1, -1]]

더 자세한 설명은 참조링크 해당 링크에서 참조하면 좋을 거 같다.