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

SW Expert Academy에서 학습용으로 문제를 가져왔습니다. 문제가 될 시 수정, 삭제하겠습니다.

https://swexpertacademy.com/main/main.do

문제 : 
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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

input

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

output

#1 1
#2 1
#3 1

code

Test_case=int(input())

def DFS(start, end): #DFS함수를 만드는데 시작과 끝을 인자로 받는다.
    stack=[]         #빈 스택 생성
    visited=[False]*(V+1)  #경로에 있는지 없는지 확인
    stack.append(start)    #start인수를 스택에 추가

    while stack:           #stack이 비어있는 동안
        now=stack.pop()    #stack을 pop으로 꺼내 현재값 지정
        visited[now]=True  #현재값이 방문했다면
        for i in range(1, V+1):  #1부터 V까지의 숫자까지(V는 가장 큰 숫자)
            if not visited[i] and node[now][i]: #만약 i번째에 방문하지 않고 연결되어있다면
                stack.append(i) #경로로 될수 있으므로 stack에 추가해준다.
    if visited[end]: #만약 끝점을 갔었다면
        return 1    #1을 반환하고
    else:
        return 0    #아니면 0을 반환한다.


for t in range(1,Test_case+1):
    V, E=map(int,input().split()) #V는 가장큰 숫자, E는 경로의 수(간선의 수)
    node=[[0 for i in range(V+1)] for j in range(V+1)] #리스트 내포기능으로 노드를 행렬형태로 0을 채워 만들어준다. 
    for _ in range(E): 
        start, end=map(int, input().split())
        node[start][end]=1

    start, end=map(int, input().split())
    print("#{} {}".format(t, DFS(start,end)))