22868. 산책 (small)

https://www.acmicpc.net/problem/22868

22868번: 산책 (small)

Solution

from collections import defaultdict
from queue import Queue
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
s, e = map(int, input().split())
for node in range(n):
    graph[node].sort()

def bfs(goal):
    while(not que.empty()):
        parent = que.get()
        level = len(parent)
        for child in graph[parent[-1]]:
            if child == goal:
                return parent + [child]
            if height[child] >= level:
                que.put(parent + [child])
    	        height[child] = level

height = [n] * (n+1)
height[s] = 0
que = Queue()
que.put([s])
route = bfs(e)

ans = len(route)-1
height = [n if i not in route else 0 for i in range(n+1)]
height[s] = n
que = Queue()
que.put([e])
route = bfs(s)
print(ans + len(route) - 1)

• height는 각 노드가 선택된 level의 값이 들어간다.
• height를 n으로 초기화하고, 첫 스타트인 s에는 0을 대입한다.
• queue에 s를 넣고 bfs를 돌린다.
  • 앞으로 queue에는 지금까지의 루트가 포함된 리스트가 들어간다. 자식을 넣은 후에 빼면서 유효성 검사를 하면 메모리를 너무 많이 차지하므로 큐에 넣기 전에 유효성 검사를 한다.
  • 하나씩 꺼내면서 e가 나오면 해당 루트를 반환한다.
  • e가 아니면 자식들 중 넣을 수 있는 지 높이를 보고 판단한다.
  • 방문 여부를 true false로 하지 않고 높이 개념으로 한 이유는 같은 높이에서 방문했던 노드는 후보에 포함시키기 위함이다.
  • 넣을 수 있는 자식들은 지금 꺼낸 부모 맨 뒤에 추가해서 큐에 넣는다.
  • 각 층의 level은 큐에서 꺼낸 리스트의 길이이다.
• 그 루트에 있는 것들만 높이를 0으로 바꾸고 나머진 n으로 초기화한다.
• for문과 if else 문을 한 줄로 하여 리스트를 만들었다.
• 큐를 초기화하고 e를 넣고 다시 bfs를 수행한다.