16166 백준 파이썬

오랜만의 DFS

무엇을 리스트와 딕셔너리에 저장할지 고민하는데 시간이 많이 걸렸다.

 

중요한 건 " 환승 "이다. 따라서 환승 못하는 역들에 대해서는 굳이 dfs연산을 할 필요가 없다.

환승 할 수 있는 것들은 h[x]의 길이가 2보다 크다. 이것들에 대해서만 dfs연산을 진행했다.

def dfs(start, dest,cnt):
    havetogo=[]
    for x in route[start]:
        if x==dest:
            return cnt
        if len(h[x])==1 and x not in vis: #환승 못하는 것들
            vis.append(x)
        else:
            if x not in vis:
                vis.append(x)
                havetogo.append(x)
    for x in havetogo:
        return dfs(x, dest,cnt+1)
n=int(input())
vis=[0]
h={}
route={}
for x in range(1,n+1):
    l=list(map(int,input().split()))
    for y in l[1:]:
        if h.get(y):
            h[y].extend([x])
        else:
            h[y]=list()
            h[y].extend([x])
        if route.get(y):
            route[y].extend(l[1:])
        else:
            route[y]=l[1:]
dest=int(input())
c=dfs(0,dest,0)
if c==None:
    print(-1)
else:
    print(c)

 

아래는 vis 리스트 대신 딕셔너리로 해결한 코드이다.

 

def dfs(start, dest,cnt):
    havetogo=[]
    for x in route[start]:
        if x==dest:
            return cnt
        if len(h[x])==1 and not vis.get(x): #환승 못하는 것들
            vis[x]=1
        else:
            if not vis.get(x):
                vis[x]=1
                havetogo.append(x)
    for x in havetogo:
        return dfs(x, dest,cnt+1)
n=int(input())
vis={}
vis[0]=1
h={}
route={}
ck={}
for x in range(1,n+1):
    l=list(map(int,input().split()))
    for y in l[1:]:
        if h.get(y):
            h[y].extend([x])
        else:
            h[y]=list()
            h[y].extend([x])
        if route.get(y):
            route[y].extend(l[1:])
        else:
            route[y]=l[1:]
dest=int(input())
c=dfs(0,dest,0)
if c is None:
    print(-1)
else:
    print(c)

 

 

 

의문점은 리스트가 딕셔너리랑 비슷할 뿐아니라 오히려 더 빨랐다는 점이다.

왜이렇지?