[Gold V] 4연산 - 14395 (BFS)

[Gold V] 4연산 - 14395

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

풀이 방법

첫 번째로 알고리즘 분석을 통해 BFS를 사용해야 한다는 것을 도출해내기엔 성공했다. 그러나 두 가지의 실수(실력)가 있었다.

1. 메모리 초과

주어지는 입력값 s, t의 범위를 보면 10^9까지인데, BFS를 돌리려면 방문체크를 해줘야하므로 최악의 경우 방문 체크할 배열을 10^9개 만들어야한다. 그러면 당연히 메모리 초과가 나는 것. 

이 부분에서 시간을 꽤 소모했는데, 결국 오랜 고민끝에 간단한 해결법을 생각해냈다. 그것은 바로 딕셔너리로 값을 저장하는 방법이었다. 또한 set()으로도 가능하다고 한다. 왜냐하면 set에서 방문여부를 찾는 것은 list(O(n))와는 다르게 O(1) 시간복잡도가 걸리기 때문이다.

2. 사전 순 앞서는 것 출력.

처음에 탑 바텀식을 이용하여 t에서 s를 찾아가는 방법을 선택했다. 테스트 케이스는 다 맞았지만 코드를 제출했을 때 41%에서 틀렸습니다. 가 뜨고마는데,, 다양한 풀이를 찾아보니 모두 바텀 탐 방식을 이용하는 것을 보고 분석을 시작했다.

잘 생각해보니 문제에서 답이 여러 개일 경우 사전순으로 앞선 것을 출력한다는 말이 바텀 탑 방식을 이용해야한다는 것을 증명해주는 것 같았다. 나는 당연히 제곱 => 더하기 => 빼기 => 나누기 방식을 탑 바텀식에서 적용하여 reverse하여 거꾸로 출력해주면 될 줄 았았지만, 생각보다 잘 되지 않고 오히려 헷갈렸다.

그래도 아직 미련은 못 버려서 조금씩 더 분석해보고 있는 중.. 일단은 굳이 역으로 풀 필요는 없다는 것은 확실하다.

 

from collections import deque, defaultdict

s, t = map(int,input().split())
visited = defaultdict(str)
q = deque()
q.append(s)
if s == t:
  print(0)
else:
  answer = -1
  while q:
    x = q.popleft()

    if x == t:
      answer = visited[x]
      break
    # 곱하기
    nx = x**2
    if 0 <= nx <= t and visited[nx] == "" and s != nx:
      visited[nx] = visited[x] + "*"
      q.append(nx)

    nx = x*2
    if 0 <= nx <= t and visited[nx] == "" and s != nx:
      visited[nx] = visited[x] + "+"
      q.append(nx)
    
    nx = 0
    if visited[nx] == "" and s != nx:
      visited[nx] = visited[x] + "-"
      q.append(nx)

    if x != 0:
        nx = 1
        if visited[nx] == "" and s != nx:
            visited[nx] = visited[x] + "/"
            q.append(nx)

  print(answer)