2019.03.04) 백준 완전탐색 특집 2편 - 1697 (PyPy3)

bfs를 사용하면 된다는 것은 바로 감이왔다.

방법을 2가지를 만들었다.

첫째는 이미 간 곳을 count로 저장하여 돌아가는 로직

둘째는 이중 반복으로 q를 끝까지 다 돌아야지 count를 1씩 올리는 로직

1번

a, b = map(int, input().split(' '))
 
# 카운터 저장용
visited = [-1 for i in range(100002)]
# 첫번째 카운터는 0
visited[a] = 0
# 큐에 넣기
q = [a]
 
 
while q:
    # 앞쪽 값을 뺴옴
    now = q.pop(0)
    # 결과값이랑 같으면 출력
    if now == b:
        print(visited[now])
        break
    # 지금값에 2배한게 한계를 안넘으면
    if now * 2 < 100001:
        # 만약 탐색된적이 없다면
        if visited[now * 2] == -1:
            # 카운터를 저장
            visited[now * 2] = visited[now] + 1
            # 큐에 삽입
            q.append(now * 2)
        # 탐색되었었다면
        else:
            # 카운터가 적은쪽을 넣음
            visited[now * 2] = min(visited[now] + 1, visited[now * 2])
    # 지금값에 +1 한게 한계를 안넘으면 위와같이
    if now + 1 <= 100001:
        if visited[now + 1] == -1:
            visited[now + 1] = visited[now] + 1
            q.append(now + 1)
        else:
            visited[now + 1] = min(visited[now] + 1, visited[now + 1])
    # 지금값에 -1 한게 음수가 안되면 위와같이
    if 0 <= now - 1:
        if visited[now - 1] == -1:
            visited[now - 1] = visited[now] + 1
            q.append(now - 1)
        else:
            visited[now - 1] = min(visited[now] + 1, visited[now - 1])
 
 
 
 
 
 

2번

a, b = map(int, input().split(' '))
 
# 단순 방문 확인용
visited = [False for i in range(100002)]
q = [a]
 
count = 0
 
while q:
    # 만약 지금 큐에 결과값이 있으면
    if b in q:
        print(count)
        break
    # 그냥 반복문 돌리면 실사간으로 줄어들어서..?
    l = len(q)
    # 큐 길이만큼 반복
    for _ in range(l):
        # 앞에있는 값 뺌
        now = q.pop(0)
        # 전부 한계가 안넘고 방문하지 않았다면 추가
        if now * 2 < 100001 and not visited[now * 2]:
            q.append(now * 2)
            visited[now * 2] = True
        if now + 1 <= 100001 and not visited[now + 1]:
            q.append(now + 1)
            visited[now + 1] = True
        if 0 <= now - 1 and not visited[now - 1]:
            q.append(now - 1)
            visited[now - 1] = True
    count += 1