12851. 숨바꼭질 2

5 17

4 2

import sys from collections import deque read = sys.stdin.readline n, k = map(int, read().split()) dist = [-1] * 100001 # 시작노드부터의 거리(시간) ( bfs 레벨) cnt = [0] * 100001 # 경우의 수 def bfs(v): deq = deque([v]) dist[v] = 0 # 시작노드 자기자신은 거리 0 cnt[v] = 1 # 시작노드 자기자신 경우의수 1 기본세팅 flag = 0 while deq: for _ in range(len(deq)): x = deq.popleft() # 이번 레벨에 찾는 노드가 있으므로 이번 레벨 탐색끝나면 탈출 # 이번 레벨에 동일 노드 있을 수 있으므로 바로 탈출하면은 안 됨 => flag 설정 if x == k: flag = 1 for nxt in (x - 1, x + 1, x * 2): if 0 <= nxt < 100001: # 범위 설정안하면 반례 생김 if dist[nxt] == -1: # 방문하지 않은 노드 # 시작노드로부터 현재노드의 거리 = 부모노드의 거리 + 1 dist[nxt] = dist[x] + 1 # 경우의 수는 부모에게서 그대로 물려받음 cnt[nxt] = cnt[x] # 큐에 추가 deq.append(nxt) # 방문한 노드이고, 같은 레벨에 존재하는 노드라면 elif dist[nxt] == dist[x] + 1: # 마찬가지로 부모의 경우의 수를 더해줌 cnt[nxt] += cnt[x] if flag == 1: print(dist[k]) print(cnt[k]) break bfs(n)

import sys from collections import deque read = sys.stdin.readline n, k = map(int, read().split()) visited = [0] * 100001 def bfs(v): deq = deque([(v, 0)]) # (node번호, 루트노드부터의 거리) cnt = 0 flag = 0 while deq: for _ in range(len(deq)): # 레벨 단위 실행을 위한 for문 x, dist = deq.popleft() visited[x] = 1 # 여기서 방문처리를 함! 정석적인 bfs 보다 늦게 방문처리를 함. if x == k: # 원하는 노드를 발견했지만 이번 레벨 끝까지 돌아야하므로 바로 끝내지는 않는다. flag = 1 # 이번 레벨 끝나고 탈출하기 위해서 cnt += 1 # 개수 증가 for nxt in (x - 1, x + 1, x * 2): if 0 <= nxt < 100001: # 범위 설정안하면 반례 생김 if visited[nxt] == 0: # 방문하지 않은 노드이면 deq.append((nxt, dist + 1)) # 거리증가시켜서 큐에 추가 # 탈출 if flag == 1: print(dist) print(cnt) break bfs(n)