[파이썬] 4871. 그래프 경로

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오.

두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.

예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경로를 찾는 경우, 경로가 존재하므로 1을 출력한다.
 

 

노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

 
 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50
 

다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5≤V≤50, 4≤E≤1000
 

테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 출발 도착 노드로 간선 정보가 주어진다.
 

E개의 줄 이후에는 경로의 존재를 확인할 출발 노드 S와 도착노드 G가 주어진다.

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

입력	출력
3 6 5 1 4 1 3 2 3 2 5 4 6 1 6 7 4 1 6 2 3 2 6 3 5 2 5 9 9 2 6 4 7 5 7 1 5 2 9 3 9 4 8 5 3 7 8 1 9	#1 1 #2 1 #3 1

 

🎈 나의 풀이

 

 

🎀 다른사람 풀이

 

def DFS(start):
    global result
    visited[start] = 1			# 방문 처리
    for next in range(1, v+1):
        if MyMap[start][next] and not visited[next]:  # MyMap[start][next]가 1이고 visited[next]가 0
            if next == end_node:
                result = 1
                return
            DFS(next)

TC = int(input())
for tc in range(1, TC+1):
    v, e = map(int, input().split())		# 노드, 간선
    MyMap = [[0]*(v+1) for _ in range(v+1)]		# 노드 별 경로 
    visited = [0] * (v+1)					# 방문한 노드 
    for i in range(e):
        start, end = map(int, input().split())
        MyMap[start][end] = 1		# start: 시작 노드, end: 시작 노드와 연결된 노드

    start_node, end_node = map(int, input().split())
    result = 0
    DFS(start_node)
    print(f'#{tc} {result}')

 

MyMap을 v보다 1보다 크게 생성해서 노드 번호에 맞게 구현하기 위해 0인덱스는 안 쓴다

간선의 갯수만큼 반복하면서 start, end에 입력 받은 값을 할당한다. MyMap[start][end]에 1을 넣는다. start와 end가 간선으로 연결되어있음을 의미.

visited의 start인덱스에 1을 넣어서 방문 처리한다.

1부터 v+1까지 반복한다(노드 번호에 맞추기 위해).

MyMap[start][end]가 1이고 visited[next]가 0이면 true다. start와 end가 연결되어 있고 방문한 적 없는 노드라는 의미.

next와 end_node가 같다면 result를 1로 초기화하고 끝낸다.

그렇지 않다면 재귀호출을 한다.