백준 25418 정수 a를 k로 만들기(BFS 기초 - 1차원배열)

25418번 - 정수 a를 k로 만들기

해당 문제는 1차원 배열에서 많은 경우의 수 중 최단거리를 찾는 문제이다.
이러한 많은 경우의 수에서 최단 거리를 찾는 문제는 보통 BFS를 많이 쓴다.

주어진 문제의 규칙은 정수+1, 정수x2 두 가지이다.
이 규칙은 2차원 배열에서의 BFS를 풀 때 이동방향을 체크하는 것과 동일하다.

from collections import deque

def bfs(start):
    que = deque([(start, 0)])
    visit[start] = 1

    while que:
        top, cnt = que.popleft()
        if top == k:
            return cnt
        for i in [top + 1, top * 2]:
            if not visit[i] and i <= k:
                    visit[i] = 1
                    que.append((i, cnt + 1))

a, k = map(int, input().split())
visit = [0] * (k*2 + 1)     # 이 부분 주의. k가 최대 움직일 수 있는 거리는 k*2이므로

print(bfs(a))

주의할 점

1. visit의 길이를 x2만큼 늘려야한다.

2. que에는 (노드, 움직인 횟수)를 넣어야하기에, 튜플로 만들어준다.

3. i는 k와 같기까지만 탐색하면 되므로 이 부분을 처리해줘야한다.

4. while에서 que를 꺼낼 때, 맨 앞에 탈출조건을 만들어 주는 것이 좋다.

12852 - 1로 만들기 2

이 문제는 bfs가 선택한 경로를 출력해야한다. 또한, 움직이는 루트는 /3, /2, -1로 세 가지이다.

여기서 중요한 점은, /3과 /2의 방향은 나눌 수 있을 때만 선택되기 때문에, -1은 if문으로 처리하지 않는다.

from collections import deque

def bfs(start):
    que = deque()
    que.append((start, [start]))

    while que:
        top, path = que.popleft()

        if top == 1:
            return len(path) - 1, path

        if not visit[top]:
            visit[top] = 1
            if top % 3 == 0:
                que.append((top // 3, path + [top // 3]))
            if top % 2 == 0:
                que.append((top // 2, path + [top // 2]))
            que.append((top - 1, path + [top - 1]))



n = int(input())
visit = [0] * (n+1)
path_res, path = bfs(n)
print(path_res)
print(*path)

중요한 점은 큐에 넣는 값이 (노드, 경로 배열)이라는 점이다. 마지막에 *을 통해 배열을 해제하면 끝난다.