[백준 22868번] 산책(small) (파이썬)

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

22868번: 산책 (small)

그래프+bfs에 대한 개념이 있으면 풀 수 있는 문제.

시작->도착

도착->시작

두 사이의 bfs를 구해서

이동거리를 구하면 됩니다.

 

그런데, 이 문제에서 구현해야 할 것이 하나 있습니다.

바로 '이미 갔던 지점은 가지 않는다'라는 조건.

시작->도착에서 갔던 지점은

도착->시작에서는 갈 수 없습니다.

예를들면 1,2,3,4,5 까지 길이 있고

1->3까지 간다고 가정해보겠습니다.

 

1->3으로 갈 때는

1->4->3으로 갔다고 해봅니다.

그럼 중간에 4를 지나갔네요?

그럼 3->1로 갈 때에는

4로 이동하는 경우는 제외합니다.

 

#백준 22868번 산책(small)
from collections import deque
from copy import deepcopy
N,M=map(int,input().split())

graph=[[]for _ in range(N+1)]

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 i in range(1,N+1):
    graph[i].sort()

visited=[False]*(N+1)
def bfs(start,end):
    global sett
    q=deque()
    q.append([start,0,set()])

    visited[start]=True
    visited[end]=False
    while q:
        now,cnt,setting=q.popleft()
        if now==end:
            sett=setting
            return cnt

        for go in graph[now]:
            if visited[go]==False:
                tmp_setting=deepcopy(setting)
                tmp_setting.add(go)
                visited[go]=True
                q.append([go,cnt+1,tmp_setting])

sett=set()
way1=bfs(S,E)

visited=[False]*(N+1)
#지나갔던 경로는 이용하면 안되니, visited했다고 넣는다
for po in sett:
    visited[po]=True

way2=bfs(E,S)

print(way1+way2)

 

저같은 경우에는 set()을 이용했는데

제출하고 구글링해보니

다양한 방식이 있었어요.

어떤 방법이 되어든 간에

이전 경로를 받아줄 수 있으면 됩니다.

 

bfs경로를 어떻게 받아줄 지 공부할 수 있는 문제입니다.