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

사전 순으로 출력해라하면

바로 떠올려야된다.

for i in range(n):

  graph[i].sort()

위 과정을 빼먹으면 90%에서 오답처리 된다.

 

처음엔 dfs로 했었다.

dfs는 경로 파악이 쉽고 직관적이니까

하지만 시간초과가 났다.

잠시 까먹었다. 

최단 거리 문제는 bfs로 해결해야 된다는 것을

 

문제 풀이 과정은 bfs를 2번 한다.

(1)s에서 e로 가는 최단 경로 찾기

(2)e에서 s로가는 최단 경로 찾기

 

e에서 s로 갈 때 (1)과정에서 방문한 노드는 방문하면 안되니

x,path=q.popleft()

q.append((y,path+[y])

각각 큐마다 자신이 걸어온 경로를 저장시키는 방식으로 해결했다.

 

import sys
from collections import deque
from itertools import combinations
 
sys.setrecursionlimit(10000)
 
def bfs(x):
 
     q.append((x,[x])) 
     
     while q:
         x,path=q.popleft()
         
         if x==e:
             for x in path:
                 res.append(x)
             return
         for y in graph[x]:
             if ch[y]==-1:
                ch[y]=1
                q.append((y,path+[y]))
 
def etos(x):
 
     q.append((x,[x])) 
     
     while q:
         x,path=q.popleft()
         #print(x,path)
         if x==s:
             for x in path:
                 res.append(x)
             return
         for y in graph[x]:
             if ch[y]==-1:
                ch[y]=1
                
                q.append((y,path+[y]))
 
               
 
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
    
    ## 정점 개수와 간선 개수 입력 받기
    n,m=map(int,input().split()) ##n=정점의 개수,m=간선의 개수
 
 
    ## 간선 정보 입력 받기
    graph=[[]*n for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        graph[a].append(b)
        graph[b].append(a)
 
    for i in range(n):
        graph[i].sort()
    q=deque()
    ch=[-1]*n
    ## 출발점과 도착점 세팅
    s,e=map(int,input().split()) ## s=출발점,e=도착점
   
    ans=0
    s-=1
    e-=1
    ch[s]=1
    res=[]
    bfs(s)
    
    #print(res)
    ch=[-1]*n
    for x in res:
        ch[x]=1
    ch[s]=-1 ##출발점은 가야하니까 방문 해제
    #print(ch)
    q=deque()
    
    etos(e)
    
    print(len(res)-2)