[Python-CodingTest] 6-15. 경로 탐색 (그래프 DFS: Depth First Search)

경로 탐색

문제 정리

입력

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

처리 과정

1. 인접행렬 리스트(g[][])와 방문할 노드를 체크 할 리스트(visited[]) 생성한다.
2. 인접행렬 리스트를 초기화한다.
3. DFS()가 끝나는 시점은 노드번호(=v)와 도착 노드(=n)가 같아질 때이다.
4. 1번 노드부터 n(문제에서는 5)번 노드까지 돌면서
5. 인접행렬 리스트에 1로 표시되어 있으면서 아직 방문하지 않은 노드인지 확인한다.
6. 5번 조건에 부합하면 방문 리스트(visited[])에 방문 체크(=1)한 뒤에 DFS()를 재귀 호출한다.
7. DFS() 호출하고 back 할 때는 방문 리스트(visited[])에 체크를 해제(=0)한다.

출력

6

풀이

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

def DFS(v): # v는 노드 번호
    global cnt
    if v==n:
        cnt+=1
        # for x in path:
        #     print(x,end=' ')
        # print()
    else:
        for i in range(1,n+1): # i는 1부터 5까지 # i는 방문하려는 노드 번호
            if g[v][i]==1 and visited[i]==0: # v는 현재 위치하고 있는 노드 # i노드가 간선으로 연결되어있어야 하고 이미 방문한 노드가 아니어야함
                visited[i]=1
                # path.append(i) # 방문할 노드인 i를 넣기
                DFS(i)
                # path.pop() # 🌟 back 할 때는 경로에서 pop
                visited[i]=0 # back 할 때는 방문 체크를 풀어주어야 함

if __name__=="__main__":

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

    g=[[0]*(n+1) for _ in range(n+1)] # 인접행렬 그래프 (인덱스 0번은 사용X)
    visited=[0]*(n+1) # 방문한 노드를 체크 할 리스트

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

    cnt=0
    visited[1]=1 # 1번 노드부터 시작이니까 1번 노드는 방문으로 처리

    # path=[] # 1번 노드부터 N번 노드로 가는 경로 리스트
    # path.append(1) # 1번은 무조건 넣어주어야 함

    DFS(1) # 1번 노드부터 시작
    print(cnt)

1번 노드부터 N번 노드로 가는 경로들까지 출력하려면 주석 해제!

정리

• 노드로 이동하기 전에 확인해야할 사항은 두가지!

  1. 방문할 노드가 간선으로 연결되어있는지 (g[][]==1)
  2. 방문할 노드가 이미 방문했던 노드가 아닌지 (visited[]==0)

• 경로들을 출력하는 방법까지 알아두자🙂

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기