[백준 9019] DSLR (C++)

A. 문제설명

www.acmicpc.net/problem/9019

9019번: DSLR

문제에 대한 자세한 설명은 링크 참조

 

1. D/S/R/L 4개의 명령을 수행하는 레지스터가 존재

2. 각 명령에 대한 설명은 아래와 같음

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이 된다.

3. 여기서 서로 다른 두 정수 A, B가 주어졌을 때, A에서 B로 변환하는 최단의 명령조합을 출력할 것

 

B. 접근법

BFS + 극한의 상수 최적화

 

먼저 나는 정말 단순하게 BFS로 각각 D/S/L/R에 대한 함수를 구현하여 접근하였다. 결과는 시간초과였다. 정말 많은 부분을 고민하면서 문제를 해결하려 했으나 실패했다.

 

Rebas 블로그(rebas.kr/764)에서 다시 그 해답을 찾아 알고리즘을 최적화한 결과 통과할 수 있었다. 문제의 핵심은 다음과 같다.

1. D/S/L/R의 연산을 함수호출이 아닌 연산식(Expression)의 배열로 인라인한 것: 여기서 각각의 연산들은 전부 변수에 대한 상수 계산으로 처리되므로 함수 오버헤드를 발생시킬 필요가 없다.

2. 탐색경로는 명령신호와 같이 배열에 넣고 목적지 도달시 B에서 A로 백트랙킹하여 그걸 다시 뒤집음: 경로 배열 map[]과, 명령 배열 cmd[]를 사용하였다.

 

알고리즘이 직관적으로 이해가 잘 안갈 수 있는데 표를 그려 표현하면 아래와 같다.

Ex) A:1234에서 B:3412로 탐색

b	1234	2341	3412
map[b]	-	1234	2341
cmd[b]	-	L	L

표에서 보듯이, b는 처음에 출발점에서 탐사를 시작하여 해당 연산결과가 도달되지 않았을 시, map[]에 목적지->출발지를 연결한다. 그리고 cmd[]에는 해당 연산의 이름을 넣어놓는다.

마지막에 B:3412에 도달성공시, 역순으로 다시 출발지를 찾아나서면 된다.

(map[3412] = 2341, cmd[3412], L) -> (map[2341] = 1234, cmd[2341], L) -> 1234 도달, 종료

 

C. 풀이

1. BFS 큐는 출발점에서 탐사를 시작하여 D/S/L/R 연산을 수행

2. D/S/L/R 연산을 수행한 결과가 도달되지 않았을 시, map[]에 목적지->출발지를 연결, cmd[]에는 해당 연산의 이름을 넣음

3. 목적지 도달시, 다시 역순으로 출발지까지 명령어들을 찾아 벡터에 삽입

4. 마지막으로 벡터를 뒤집고 출력함

 

D. 내 코드