DSLR

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

9019번: DSLR

문제요약:

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

   다음과 같이 4개의 조건으로 숫자들을 바꿀 수 있을 때, A 에서 B로 바꾸는데 걸리는 최소 명령어를 구하여라

 

난이도:

골드4

 

소요시간:

40+15분

 

제출횟수:

2회

 

첫번째 코딩:

import sys
import heapq as hp
input = sys.stdin.readline

graph = [[] for _ in range(10000)]
INF = int(1e9)
for i in range(10000):
    #DSLR
    graph[i].append((2*i)%10000)
    graph[i].append(i-1 if i!=0 else 9999)
    graph[i].append((i*10)%10000+(i*10)//10000)
    graph[i].append((i%10)*1000+ i//10)

def dijkstra(start,end):
    distance = [[INF,'1'] for _ in range(10000)]
    q = [[[0,''],start]]

    while q :
        dist,now = hp.heappop(q)
        if dist[0]>distance[now][0]:
            continue

        for l,i in enumerate(graph[now]):
            cost = dist[0]+1
            if distance[i][0]>cost:
                distance[i] = [cost,dist[1]+str(l)]
                hp.heappush(q,[[cost,dist[1]+str(l)],i])
    return distance[end][1]

change_DSLR = {'0':'D','1':'S','2':'L','3':'R'}

n = int(input())
for _ in range(n):
    a,b = map(int,input().split())
    for i in dijkstra(a,b):
        print(change_DSLR[i],end ='')
    print()

먼저 조건에 맞게 각 숫자들을 각각의 노드들로 만들어 준 후, 이어주었습니다, 그 후 다익스트라 알고리즘을 통해 end까지의 최솟값을 찾고 그때그때 각각의 최소 경로들을 저장시켜주어 반환하여 dict을 활용해 다시 DLSR 로 변환해 주었습니다.

하지만 다익스트라는 시작노드로부터 나머지 모든 노드까지의 거리를 찾는 알고리즘이고 주어진 문제에선 그렇게 할 필요가 없이 원하는 목표까지의 거리만 확인하면 되기 때문에, (또한 거리간 간격이 일정하기 때문에, 전체를 볼 필요없이 bfs로 탐색하다가 정답이 나오면 바로 끊어주면 되므로 BFS로 바꿔주어야 합니다.) > 아니면 시간초과

 

두번째 코딩:

import sys
from collections import deque
input = sys.stdin.readline

graph = [[] for _ in range(10000)]
for i in range(10000):
    #DSLR
    graph[i].append((2*i)%10000)
    graph[i].append(i-1 if i!=0 else 9999)
    graph[i].append((i*10)%10000+(i*10)//10000)
    graph[i].append((i%10)*1000+ i//10)

def bfs(start,end):
    visited =[0]*10000
    #탐색했었는지 여부 했다면, 최소길이
    q = deque([[0,start,'']])

    while q:
        dist,now,route = q.popleft()
        for l,i in enumerate(graph[now]):
            if i == end:
                return route+str(l)
            if visited[i]==0:
                #온적이 없거나 이제 새로 가는게 더 빠름
                visited[i] = dist+1
                q.append([dist+1,i,route+str(l)])
                

change_DSLR = {'0':'D','1':'S','2':'L','3':'R'}

n = int(input())
for _ in range(n):
    a,b = map(int,input().split())
    for i in bfs(a,b):
        print(change_DSLR[i],end ='')
    print()

똑같은 메커니즘이지만 bfs로 했으며 중간에 답을 찾으면 더이상 탐구하지 않고 바로 나오기 때문에 시간을 절약할 수 있습니다. 사실 dikjstra로 해도 중간에 답을 찾았을때 나왔다면 크게 차이가 나진 않습니다.