경로 탐색(그래프DFS)

내가 생각한 코드

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, s):
    global cnt
    if s == 5:
        cnt+=1
    else:
        for i in range(1, n+1):#1부터 5까지 반복
            if res[s][i] == 1 and ch[i]==0: #갈 수 있는 방향이고, 중복된 길이 아닌 경우
                ch[i] = 1
                DFS(L+1,i)
                ch[i] = 0

if __name__ == "__main__":
    n,m = map(int,input().split()) # 5 9
    res = [[0]*(n+1) for _ in range(n+1)] #이차원 0 배열
    ch = [0]*(n+1) # 체크리스트(중복방지)
    ch[1] = 1
    cnt = 0

    for _ in range(m):
        a, b = map(int,input().split())
        res[a][b] = 1 # 방향 그래프 그림

    DFS(1,1) # 배열 중 1부터 탐색 위함.
    print(cnt) 

하 두시간 생각했는데 40점 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
휴 ㅠㅠㅠㅠㅠㅠ
뭐지??

선생님 코드

일단 인덱스 0번 안쓴점이 같고... 하나 다른점은 인자를 덜 준것.

지금까지는 그러하다..

여기가 함수인데..

나는 뭐가 다른지 모르겠네 ?? 왜 결과가 다르게 나올까 ?

아@!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!아아아악

왜 5로 했냐
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
하 ㅜㅜㅜ 변수로 했어야지 ㅠㅠㅠ ;;;내가 이런다니까....

어휴 짜증나 ㅋㅋ;;;;;;;
잘 바꿨습니다 .....

+) 추가로 경로까지 출력하는 코드

간단하다

import sys
sys.stdin = open("input.txt", "rt")

def DFS(v):
    global cnt
    if v == n:
        cnt+=1
        for z in arr:
            print(z, end=" ")
        print()
    else:
        for i in range(1, n+1):
            if res[v][i]==1 and ch[i]==0:
                ch[i] = 1
                arr.append(i)
                DFS(i)
                ch[i] = 0
                arr.pop()

if __name__ == "__main__":
    n,m = map(int,input().split()) # 5 9
    res = [[0]*(n+1) for _ in range(n+1)] #이차원 0 배열
    ch = [0]*(n+1) # 체크리스트(중복방지)
    arr = []
    arr.append(1)
    for _ in range(m):
        a, b = map(int,input().split())
        res[a][b] = 1 # 방향 그래프 그림
    ch[1] = 1 #1번 노드 방문했다 친다.
    cnt = 0

    DFS(1) # 배열 중 1부터 탐색 위함.
    print(cnt) 

append 와 pop 하면 된다..