[백준] 골드4 DSLR

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

9019번: DSLR

본 문제는 0부터 9999까지의 숫자가 두개 들어오는데, 이 두 숫자를 A, B라고 하자. A에서 B로 바꾸는데 연산 4개를 이용하여 최소 연산 수를 구하는 것이다. 결국 D, S, L, R 이 4를 통한 최소 경로를 구하는 문제이므로, BFS를 통해 풀 수 있을 것이다.

 

다만 본 문제는 좀 애먹은 부분이 있다면, 시간초과 문제이다. 

L과 R 연산 같은 경우 예를 들어 1234를 L 연산한다고 해보자. 그러면 2341로 왼쪽으로 밀게되고, R 연산같은 경우 4123 으로 오른쪽으로 밀게 된다. 

 

처음 이 연산을 위해 최대한 시간복잡도를 줄이겠다는 생각이 잘못되어 deque로 1234를 str로 변환하여 담은 뒤, pop 또는 popleft를 통해 숫자들의 위치를 옮기고 다시 int형으로 바꾸는 작업을 했다. 하지만, 이 작업은 오히려 시간복잡도를 늘리는 어리석은 짓이였다.

굳이 문자열 표현으로 안바꿔도 정수형에서 모두 처리할 수 있었다.

예시) 1234 -> L연산 -> 2341

left = num // 1000

right = num % 1000

n_num = right * 10 + left

left : 1 

right : 234

next number : 234 * 10 + 1 = 2341

 

예시) 1234 -> R연산 -> 4123

left = num // 10

right = num % 10

n_num = right * 1000 + left

left : 123

right : 4

next number : 4000 + 123 = 4123

 

이렇게 하면 정수형 안에서 L, R 연산을 수행할 수 있기 때문에 시간복잡도 관여를 크게 안할 수 있게 되었다. 

다만, 두번째 문제가 발생했는데 result = [""] * 10000을 통해 각 숫자마다의 경로들을 모두 저장할 리스트를 만들었었다.

 

이유는 아직도 모르겠지만, 매번 업데이트할때

result[n_num] = result[num] + 'D' (or 'S', 'L', 'R') 라고 하면 17%에서 틀렸다고 뜬다. 

반례들을 찾아보니 이런 업데이트 과정에서 딱 한 가지 경우에서 12개의 경로가 정답인데, 13개의 경로가 출력되었다.

 

이부분은 도저히 이유를 알수가 없어서 구글링 해본 결과 deque에 숫자들을 담을때, 경로도 같이 저장하면 된다는 것이다. 

q.append((n_num, path+"D")) (or 'S', 'L', 'R')

이렇게 한뒤, q.popleft()를 통해 나오는 num이 B와 같다면 path만 출력하면 된다는 것이다.

마지막 문제였던 경로 수집을 해결하니 드디어 맞게되었다.

소스 코드 : 

시험기간이라 글은 따로 올리진 않고 있었지만, 1일 1백준은 꾸준히 실천중

1일 1백준 46일째..