[bfs/백준] 16397번 : 탈출

- 문제 : https://www.acmicpc.net/problem/16397

 

Gold Lv4 문제이고, 풀이 없이 풀었다. 생각보다 조건을 세세하게 나눴어야 해서 여러번 시도를 했던 문제이다.

 

문제 이해 

- A, B 버튼을 t번 이하로 눌러서 n을 g로 최소 시간 안에 만들 수 있는지 확인하는 문제다. 만약 못 만든다면 ANG를 출력한다.

- A 버튼과 B 버튼의 동작방식은 다음과 같다.

   A 버튼 : (이전 수) + 1

   B 버튼 : (이전 수) * 2 -> 가장 큰 자릿수 - 1

- 실패하는 케이스도 잘 생각해야하는데, 만약 A버튼을 누르거나, B 버튼에서 곱하기 2를 했을 때 10 ** 6 이상이 되면 실패한 케이스이다. 

- 풀면서 헤맸던 부분은 다음과 같다.

  1. bfs인데 방문한 노드를 visit 처리하지 않았던 것

  2. 다음 노드가 범위 내(1 이상 99999 이하)여야 한다는 것이다. 

  3. A버튼과 B버튼이 이동방식이 달라서 visit 처리를 해줘야하는 노드들도 다르다.

 

풀이 로직 

- n, t, g를 입력값으로 받고, 방문하는 숫자들을 처리하기 위해 visit를 초기화 한다. (최대 숫자가 99999이므로 길이는 넉넉하게 10 ^ 5 + 1)

 

- queue에 n을 추가한 다음 while문으로 bfs를 진행한다. 

 

- 방문한 노드가 g와 같고, visit[number] - 1 값이 t 이하라면 정답이므로 visit[number] - 1을 출력한 뒤 while 문을 break한다. (visit 시작 값이 1로 시작해서 정답과 1 차이가 나기 때문에 -1을 해줬다)

 

- 방문한 노드가 g가 아니라면 다음 노드로 이동하는데, 다음 노드가 범위 내 [1, 99999]에 있는지 확인한다. 만약 다음 노드가 범위 내에 없다면 문제에서 바로 실패라고 했으므로 for문을 break한다. 

 

- 다음 노드가 범위 내에 있을 때, A 버튼인지 B 버튼인지에 따라 다음 노드 값이 달라진다. 

A 버튼인 경우는 number + 1를 방문하지 않은 경우 이동할 수 있고, 이에 따라 visit 처리하고, queue에 추가하면 된다.

if each == number + 1:
    if not visit[each]:
        queue.append(each)
        visit[each] = visit[number] + 1

B 버튼인 경우 2 * number가 다음 노드가 아니라 2배 한 뒤 최대 자리수 값을 -1 해야한다. 그래야 최종값인 temp가 된다. 

이 temp를 방문하지 않은 경우 방문 처리 후, queue에 추가하면 된다.

elif each == number * 2:
    count = len(str(each))
    temp = each - 10 ** (count - 1)
    if not visit[temp]:
        queue.append(temp)
        visit[temp] = visit[number] + 1

 

- while문을 다 돌았는데도 정답을 출력하지 못했으면 실패한 것이므로 ANG를 출력한다. 

 

정답 풀이 

항상 visit 배열로 방문 여부 확인해야 시간초과 안 뜨고, 

다음 노드가 범위 내에 있는지 확인 해야함 

이 문제에서는 다음 노드가 어디인지에 따라 노드 값이 변형될 수 있으므로 그 부분 주의하기

from collections import deque

n, t, g = map(int, input().split())

queue = deque() # 숫자, 횟수 
queue.append(n)
flag = False
visit = [0] * (10 ** 5 + 1)
visit[n] = 1
while queue:
    number = queue.popleft()
    
    if number == g:
        if visit[number] - 1 <= t:
            flag = True
            print(visit[number] - 1)
            break             
        
    for each in [number + 1, number * 2]:
        if 1 <= each <= 99999 :
            if each == number + 1:
                if not visit[each]:
                    queue.append(each)
                    visit[each] = visit[number] + 1
            elif each == number * 2:
                count = len(str(each))
                temp = each - 10 ** (count - 1)
                if not visit[temp]:
                    queue.append(temp)
                    visit[temp] = visit[number] + 1
        else:
            break
                
if flag == False:
    print('ANG')

 

 

삽질기록,,,