파이썬 알고리즘 265번 | [백준 16953번] A → B

265. A → B

1) 어떤 전략(알고리즘)으로 해결?

나는 bfs
그래프 이론
그리디 알고리즘
그래프 탐색
너비 우선 탐색

2) 코딩 설명

<내 풀이>

from collections import deque
import sys
# A를 B로 바꾸는데 필요한 연산의 최솟값
a,b = map(int, sys.stdin.readline().split())
visit = [] # 방문 여부 체크 
q=deque()
q.append((a,0)) # 값, 연산을 수행한 갯수
visit.append(a) 
# 한번 도달했던 값은 visit 이라는 배열에 추가 
chk = False 
# 가능, 불가능 여부 체크 

while q :
    now, cnt = q.popleft()
    if now==b : 
        # 만약 지금 검사하는 애가 우리가 찾던 애라면 그 연산횟수+1 출력, 프로그램 종료
        chk = True
        print(cnt+1)
        exit(0)
    elif now<=b : 
        # 만약 지금 검사하는 애가 b보다 작거나 같은 아이라면 (b보다 크면 거기에 2곱하거나 1붙이면 nono)
        if now*2<=b and now*2 not in visit : 
            # 2를 곱하는 것 - b보다 안 크고 안 같고, 방문 안했다면
            q.append((now*2, cnt+1))
            visit.append(now*2)
        if int(str(now)+"1")<=b and int(str(now)+"1") not in visit  : 
            # 1을 붙이는 것 - b보다 안 크고 안 같고, 방문 안했다면
            q.append((int(str(now)+"1"), cnt+1))
            visit.append(int(str(now)+"1"))
if chk==False : # 만약 빠져나왔는데 chk가 거짓이면 이미 글러먹은 것 
    print(-1)

< 내 틀렸던 풀이, 문제점>

(1) 메모리 초과

• visit 배열이 너무 커져서 나는 에러였다.

from collections import deque
import sys
sys.setrecursionlimit(10**5)
# A를 B로 바꾸는데 필요한 연산의 최솟값
a,b = map(int, sys.stdin.readline().split())
visit = [0 for _ in range(b+1)]
q=deque()
q.append((a,0))
visit[a]=1
chk = False
while q :
    now, cnt = q.popleft()
    if now==b : 
        chk = True
        print(cnt+1)
        exit(1)
    elif now<=b : 
        if now*2<=b and visit[now*2]==0 :
            q.append((now*2, cnt+1))
            visit[now*2]=1
        if int(str(now)+"1")<=b and visit[int(str(now)+"1")]==0:
            q.append((int(str(now)+"1"), cnt+1))
            visit[int(str(now)+"1")]=1
if chk==False :
    print(-1)

(2) exit를 0으로 안해서 난 에러 - 런타임 에러 (NZEC)

from collections import deque
import sys
# A를 B로 바꾸는데 필요한 연산의 최솟값
a,b = map(int, sys.stdin.readline().split())
visit = []
q=deque()
q.append((a,0))
visit.append(a)
chk = False
while q :
    now, cnt = q.popleft()
    if now==b : 
        chk = True
        print(cnt+1)
        exit(1)
    elif now<=b : 
        if now*2<=b and now*2 not in visit :
            q.append((now*2, cnt+1))
            visit.append(now*2)
        if int(str(now)+"1")<=b and int(str(now)+"1") not in visit  :
            q.append((int(str(now)+"1"), cnt+1))
            visit.append(int(str(now)+"1"))
if chk==False :
    print(-1)

<반성 점>

• exit(0) 으로 프로그램 종료시키기
• bfs 방문배열 너무 크게 하지 않기, 메모리초과 걸려

<배운 점>

• exit(0) 으로 프로그램 종료시키기