[Python 3] BOJ - 14395 "4연산"

 # 문제 링크

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

14395번: 4연산

 # 풀이

 개인적으로 문제의 핵심은 그래프로 모델링을 하는 것이라 생각한다. 현재 수를 노드라고 본다면, 각각의 연산은 간선이며, 이어지는 노드는 현재수에 연산을 한 결과가 된다.

<그림 1. TC 1번의 그래프 모델링>

 따라서 가중치가 모두 1인 무향 그래프와 같고, 이 때 연산의 최소값, 즉 최단거리를 구하라고 하였으므로 BFS를 통해 정답을 구할 수 있다. 또한 여러개가 답인 경우 사전순으로 앞서는 것을 출력하라고 했으므로 BFS시 곱셈, 덧셈, 나눗셈, 뺄셈 순으로 접근하면 된다. 이 때 큐에 넣는 정보는 (현재 수, 이때까지 한 연산)이 된다

 그런데 BFS의 핵심인 "이미 방문한 점을 방문해서는 안된다"를 지키기 위해 방문을 체크하는 리스트를 써야 한다. 그런데 t의 제한이 상당히 크므로 리스트를 쓸 수 없다. 따라서 방문 노드를 key, 최초 방문 시점을 value로 갖는 dict로 이를 대체할 수 있으며 sparse한 구조에 효과적이다.

 그래프 상에서 모든 연산 결과를 그리지 않았는데, 자세히 관찰하다 보면 2개의 경우가 나타남을 알 수 있다. 첫번째는 이전에 노드가 나온 경우이다. 이 때는 현재 노드를 구하기 위해 사용한 연산이 최소 연산이 아니기 때문이다. 두번째는 t의 값보다 커지는 경우이다. t의 값보다 커지면 덧셈과 곱셈은 무의미해진다. 따라서 나눗셈 연산을 해야한다. 그런데, 나눗셈 연산은 최초의 연산에서 이루어지므로, 굳이 t보다 커질때까지 기다렸다가 나누는 것보다는 처음부터 1로 나누는 것이 최소 연산임이 자명하기 때문이다.

 

 # 코드

import sys, collections

# 입력부
s, t = map(int, sys.stdin.readline().split())

if s == t:
    print(0)
else:
    q = collections.deque()
    
    # check : 현재 숫자를 key, 최초 방문 시점을 value로 갖는 dict
    check = {s : 0}
    q.append((s, ''))
    
    # op : 연산자 배열
    op = ['*', '+', '/', '-']
    while q:
        now, path = q.popleft()
        
        # 현재 수가 t라면 그 때 연산이 사전순으로 가장 앞서므로 프로그램 종료
        if now == t:
            print(path)
            sys.exit(0)
        for idx, next in enumerate([now ** 2, 2 * now, 1, 0]):
            if next > t:
                continue
                
            # check 확인 및 갱신
            if next not in check:
                check[next] = check[now] + 1
                q.append((next, path + op[idx]))
                
    # t로 바꿀 수 없는 경우
    print(-1)