[골드 4] 백준 14395 - 4연산 (파이썬)

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

풀이

from collections import deque

S, T = map(int, input().split())

visit = set()
path = {}
queue = deque()

queue.append(S)
visit.add(S)
path[S] = ""

• 입력으로 정수 S, T를 받고 BFS용 자료구조 초기화한다.
• visit는 중복 연산 방지를 위한 방문 집합을 생성하고, path는 각 숫자에 도달한 연산 문자열을 저장한다.

while len(queue) != 0 :
    u = queue.popleft()

BFS 반복문을 시작한다.

    if u * u <= 1e9 and u * u not in visit :
        queue.append(u * u)
        visit.add(u * u)
        path[u * u] = path[u] + "*"

“*” 연산을 수행해서 새로운 값이 아직 방문하지 않았고, 10억 이하이면 큐에 넣는다.

또한, 연산 문자열은 기존에 도달한 경로 뒤에 *을 추가해서 기록한다

    if u + u <= 1e9 and u + u not in visit :
        queue.append(u + u)
        visit.add(u + u)
        path[u + u] = path[u] + "+"

“+” 연산도 수행하고, 위와 동일한 방식이다.

    if u / u <= 1e9 and u / u not in visit :
        queue.append(u / u)
        visit.add(u / u)
        path[u / u] = path[u] + "/"

/ 연산을 수행하고, u / u 는 항상 1이고 float 형태가 들어간다. 여기서 path키는 1.0이 되므로, 추후에 T == 1 이라고 path[1]은 없다.

지금의 문제점.

1. u / u는 항상 1이다
2. 따라서 이 연산은 매번 같은 결과만 내고, 처음에만 의미가 있다. 그런데 이 조건문에서는 실수형 / 연산을 사용해서 정수형 set에 1.0이 들어가면서 문제 발생 가능. → // 또는 정수형 1로 비교하는 게 맞다.
3. 연산이 빠져 있음
4. 4연산이라 했을 때 +, -, *, / 모두 다뤄야 함.
5. 연산 결과를 정수로 제한하지 않음
6. u / u는 실수형 1.0이 되며, visit 집합에 float으로 들어가는데, 문제는 T가 정수이기 때문에 T in path가 실패할 수 있음.
7. BFS 종료 조건 누락
8. u == T일 때 바로 break하거나 출력하는 로직이 없어서 모든 경우 다 돌아야 함.

코드

# 백준 14395 - 4연산
# 분류 : BFS

from collections import deque

S, T = map(int, input().split())

visit = set()
path = {}
queue = deque()

queue.append(S)
visit.add(S)
path[S] = ""

while len(queue) != 0 :
    u = queue.popleft()

    if u * u <= 1e9 and u * u not in visit :
        queue.append(u * u)
        visit.add(u * u)
        path[u * u] = path[u] + "*"

    if u + u <= 1e9 and u + u not in visit :
        queue.append(u + u)
        visit.add(u + u)
        path[u + u] = path[u] + "+"
    
    if u / u <= 1e9 and u / u not in visit :
        queue.append(u / u)
        visit.add(u / u)
        path[u / u] = path[u] + "/"
    
if S == T :
    print(0)
elif T in path :
    print(path[T])
else :
    print(-1)