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

문제 링크 : https://www.acmicpc.net/problem/22868

22868번: 산책 (small)

 

짧은 경로가 사전순으로 먼저 나온것이 우선으로 되어야한다고 해서 입력으로 생성한 인접 리스트를 정렬해주고 시작했다.

 

일단 나는 두번의 BFS를 수행했다.

S에서 E로, E에서 S로 BFS를 두번 진행한다.

S에서 E로 진행할 때는 경로를 저장한다.

방문체크 할때 다음 점이 어느 점에서 왔는지 넣어 준다.

그리고 도착했을 때는 마지막 점에서 거꾸로 올라가면 S에서 E로 향하는 경로가 나온다.

이를 반환 한다.

 

그리고 반환된 path 정보를 가지고 방문배열을 재생성한다.

path에 등록된 점은 방문처리하여 E에서 S로 향할 때 방문하지 않도록 한다.

이때 시작점은 빼준다.

 

두번째 BFS는 E에서 S로 향하는 평범한 BFS를 진행하면 된다.

이때 경로의 길이를 세주면 된다.

 

나는 하나의 BFS 함수를 사용 했다.

시작, 끝점, 방문배열, 첫번째BFS인지 두번째 BFS인지 확인할 변수(start_cnt)

이렇게 4가지를 넣었다.

그래서 start_cnt가 0이라면 path를 구해주고 아니라면 경로의 총길이를 반환하면 된다.

 

두번째 BFS일때 start_cnt에 경로의 길이를 넣어주고 BFS 시작할 때 경로의 길이를 해당 값으로 넣어주고 시작한다.

그래서 최종 길이의 값이 전체 경로의 길이가 되도록 하였다.

 

from sys import stdin
from collections import deque
input = stdin.readline

n,m = map(int, input().split())

adj_list = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

for idx in range(1,n+1):
    adj_list[idx].sort()

s,e = map(int, input().split())
def solv():
    visited = [-1]*(n+1)
    visited[s] = 0
    path = bfs(s,e,visited,0)

    visited = [-1]*(n+1)
    for idx in path:
        visited[idx] = 1
    cnt = bfs(e,s,visited,len(path))
    print(cnt)

def bfs(start,end,visited,start_cnt):
    q = deque([(start, start_cnt)])
    while q:
        now, cnt = q.pop()
        if now == end:
            if start_cnt == 0:
                break
            else:
                return cnt
        for nxt in adj_list[now]:
            if visited[nxt] == -1:
                visited[nxt] = now
                q.appendleft((nxt, cnt + 1))
    path = [end]
    nxt = visited[end]
    while nxt != 0:
        path.append(nxt)
        nxt = visited[nxt]
    return path[:-1]
solv()