4871. [파이썬 S/W 문제해결 기본] 4일차 - 그래프 경로

DFS를 이용한 풀이 

 

graph에 각 노드의 간선에 대한 노드들을 넣어주고

 

전체 visit의 값에 True 를 넣고 한번 방문한 적이 있으면 False를 넣어준다

그리고 간선에 대한 노드가 True 값이면 다시 함수를 호출해 False 로 바꿔준다 

 

맨 마지막에 도착노드값이 True(방문한 적이 없음) 면 result =0 으로 해주고 그 밖에는 result = 1

def dfs(s):
    visit[s] = False
    for i in graph[s]:
        if visit[i] == True:
            dfs(i)

testCase = int(input())

for i in range(testCase):
    v,e = map(int,input().split())
    graph = [[] for _ in range(v+1)]
    visit  = [True for _ in range(v+1)] #방문여부 확인

    for j in range(e):
        a,b = map(int,input().split())
        graph[a].append(b) #각 노드별 간선들을 추가

    s,g = map(int,input().split()) #출발노드와 도착노드
    dfs(s)
    result = 1
    if visit[g]==True:
        result = 0
    print('#'+str(i+1)+' '+str(result))

계속 런타임 에러가 나서 왜인가 했더니 split(' ') 을 하면 안되는거였다 ! split() 을 해야지 해결이 됨 왜지 ..?

 

dfs랑 dp 문제들이 너무 어려워서 많이 풀어보는게 중요할듯 !