SWEA 4871 그래프 경로 (python)

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

 

파이썬 SW문제해결 기본 - Stack1

2021.06.05 - [Algorithm] - SWEA 4869 종이붙이기 (python)

2021.06.05 - [Algorithm] - SWEA 4866 괄호검사 (python)

2021.06.05 - [Algorithm] - SWEA 4871 그래프 경로 (python)

2021.06.05 - [Algorithm] - SWEA 4873 반목문자 지우기 (python)

SWEA 4873 반목문자 지우기 (python)

 

문제

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

 

코드

 

풀이 1

# 인접행렬 방식으로 풀은 것
T = int(input())

# 시작점 부터 끝점까지 도달할 수 있는지에 대한 함수
def dfs(start, end):
    # 스택 초기화
    stack = []
    # 방문 여부를 검사할 행렬
    # 인덱스 값이므로 +1을 해주어 혼동 x
    visited = [False] * (V + 1)
    # 시작점을 스택에 삽입해준다
    stack.append(start)

    # 스택이 빌때까지 반복문 돌려준다.
    while stack:
        # 지금 현재 스택을 꺼내어 현재 값에 할당
        now = stack.pop()
        # 현재 들렀다는 것을 표시
        visited[now] = True
        # 1부터 V+1범위 까지 살펴봄
        for next in range(1, V+1):
            # 만약 방문하지 않았고
            # 또한 연결되어 있다면 (값이 1이라면)
            if not visited[next] and node[now][next]:
                # 갈수있는 곳 이므로 스택에 더해준다.
                stack.append(next)
    # 만약 끝점에 들른흔적이 있다면?
    if visited[end]:
        # 들렀다는 것을 표시
        return 1
    else:
        # 아니라면 안들렸다는 것을 표시
        return 0

for tc in range(1, T+1):
    # V와 E 받아오기
    V, E = map(int, input().split())
    # 노드를 인접행렬로 나타내기 위한 0으로 이루어진 초기값
    # 인덱스 값이므로 V+1을 해주어 혼동되지 않도록 하자
    node = [[0 for _ in range(V+1)]for _ in range(V+1)]
    # 연결선 E 만큼 반복해주면서 연결되어있는가를 파악
    for _ in range(E):
        # 시작점과 끝점을 각각 받아옴
        start, end = map(int, input().split())
        # 해당하는 인접행렬에 할당해줌
        # 방향성이 있음
        node[start][end] = 1
    # 검사를 위한 시작점과 끝점의 값을 가져옴
    S, G = map(int, input().split())
    # 원하는 구간이 연결되어 있는가 검사한 값을 출력
    print("#{} {}".format(tc, dfs(S, G)))

 

풀이2

# 리스트? 방식으로 풀은 것
T = int(input())

for tc in range(1, T+1):
    # V와 E 받아옴
    V, E = map(int, input().split())
    # 리스트 방식? 으로 초기값 선언하자 노드값
    node = [[]for _ in range(V+1)]
    # E개만큼 연결되어 있기 때문에 범위 E로 설정
    for _ in range(E):
        # 각각의 연결관계를 받아오자
        start, end = map(int, input().split())
        # 연결관계를 표현하기 위해 추가해주자
        node[start].append(end)
    S, G = map(int, input().split())
    # 스택초기값
    stack = [S]
    # 방문검사
    visited = [False for _ in range(V+1)]
    # 스택이 존재하지 않을때 까지 반복
    while stack:
        # 현재 값을 스택에서 꺼내옴
        now = stack.pop()
        # 방문했다고 표시해줌
        visited[now] = True
        # 현재 노드의 정보 중에서
        # 각각의 리스트 들은 n번이 이어진 숫자들을 담고있다
        # 이중에서 반복문을 돌려서 검사를 한다.
        for next in node[now]:
            # 만약 다음 갈곳이 반복한적이 없던것이 있으면
            if not visited[next]:
                # 스택에 다음 갈곳의 정보를 넘겨준다.
                stack.append(next)
        # 이과정을 갈곳이 없을때 까지 반복

    # 출발점에서 시작해서 반복을했는데
    # 내가 말한곳에 다녀온적 있어? 도장찍어왔어?
    if visited[G]:
        # 왔으면 잘했어
        result = 1
    else:
        # 아니면 0...
        result = 0

    print("#{} {}".format(tc, result))