백준_12851 (숨바꼭질2_1차원 배열 BFS - 다시 풀어보기)

• 링크 : https://www.acmicpc.net/problem/12851
  

---

메모한 것

• 숨바꼭질 1이랑 똑같네

• 가장 빠른 시간 => BFS 최단경로

• 이동하는 경우 -1과 1 그리고 * 2

• 주의사항은 가장 빠른 시간으로 찾는 방법이 몇 가지인지 이므로

  • 최단경로로 가는 케이스를 처음으로 찾으면 print() 후 return이 아니라
  • 그 결과를 return해서 append()나 += 를 해줘야할듯

---

1차적으로 풀어본 - 답 아님 (나중에 다시 풀어볼것)

''' 내가 푼 (A->B 문제 이후) <graph 사용하지 않고, 1차원 배열 BFS 문제> '''
from collections import deque

def bfs():
    que = deque()
    que.append((n, 0))
    
    min_dist = 0
    
    answer = 0 # 방법의 수
    
    while que:
        now, cnt = que.popleft()
        
        if k < now:         # (주의 중요) next가 아니라도 이렇게 해도 ㄱㅊ
            continue
        if k == now:
            answer += 1
            min_dist = cnt
        
        que.append((now-1, cnt+1))
        que.append((now+1, cnt+1))
        que.append((now*2, cnt+1))
    else:        
        print(min_dist)
        return answer 
        

n, k = map(int, input().split())
print(bfs())

---

블로그 보고 한 것

블로그 보고 한것 (https://velog.io/@dhelee/백준-12851번-숨바꼭질4-Python-너비-우선-탐색BFS)

• 다른 방법1 : https://chul2-ing.tistory.com/71

• 내가 생각하지 못한 내용은 다음과 같음

1. 일단 visit을 2차원 리스트로 만들어서
   • [ 도달하는데 걸린 시간, 경우의 수 ] 로 저장
   • [[-1, 0], [-1, 0], ..., [-1, 0]]
2. 처음 도달하는 경우 vs 아닌 경우 두 가지로 나눠야 하는듯
   • 처음 도달한다면 (시간과 경우의수 ++)
     • visit[이동 위치][도달하는데 걸린 시간] = visit[이전 위치][이전위치의 시간] + 1
     • visit[이동 위치][경우의 수] = visit[이전 위치][이전위치의 경우의 수] + 1
   • 처음 아니면 (경우의 수만 ++)

• visit[이동 위치][경우의 수] = visit[이전 위치][이전위치의 경우의 수] + 1

''' 블로그 - 매번 경우의 수를 갱신하는 '''
from collections import deque

def bfs(n):
    q = deque([n])
    visited[n][0] = 0
    visited[n][1] = 1 
    
    while q:
        x = q.popleft()
        
        for i in [x - 1, x + 1, x * 2]:
            if 0 <= i <= 100000:
                if visited[i][0] == -1:                 # 처음 도달한다면
                    visited[i][0] = visited[x][0] + 1   # 걸린 시간 저장
                    visited[i][1] = visited[x][1]       # 경우의 수 저장
                    q.append(i)
                    
                elif visited[i][0] == visited[x][0] + 1: # 처음이 아니라면 (하지만 최단 시간이라면)
                    visited[i][1] += visited[x][1]       # 경우의 수 갱신
                    
n, k = map(int, input().split())
visited = [[-1, 0] for _ in range(100001)] # [지점 i에 도달하는데 걸린 시간, 경우의 수]

bfs(n)
print(visited[k][0])
print(visited[k][1])

''' https://chul2-ing.tistory.com/71 '''
from collections import deque         

n, k = map(int, input().split())
graph = [0] * 100001  # (중요) 그래프 사이즈는 항상 이렇게 넉넉히

#bfs
ans_count = 0   # 최소 시간
ans_way = 0     # 방법의 수

que = deque()
que.append(n)

while que:
    now = que.popleft()
    cnt = graph[now]
    
    # 이 유형(1차원 BFS) 의 경우 먼저 찾으면 break 또는 continue하는 전처리를 미리 수행
    if now == k:
        ans_count = cnt       # 최소 시간
        ans_way += 1          # (중요) 이게 핵심 {방법의 수}
        continue             # (중요) 이게 핵심 -> 찾아도 continue
    
    # 이동 시 못찾았으면 다음 위치로 이동을 진행해주는 것
    for nx in [now-1, now+1, now*2]:
        if 0 <= nx < 100001:
            # (매우 중요) 처음가거나 or nx에 방문할 visited가 이미 기록되어 있더라도, 
            # 현재 x 까지 길이 + 1 만큼과 동일하다면 같은 레벨이라고 할 수 있다.
            if graph[nx] == 0 or graph[nx] == graph[now]+1:
                que.append(nx)
                graph[nx] = cnt + 1
                
print(ans_count)
print(ans_way)