2644

날짜 : 2022. 11. 21

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())  # 전체 사람의 수
visited = [False] * (n + 1)
start, end = map(int, sys.stdin.readline().split())  # 시작, 끝
cnt = 0
t = int(sys.stdin.readline())  # 관계 개수
family = [[] * (n + 1) for i in range(n + 1)]

for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    family[a].append(b)
    family[b].append(a)


def dfs(node, move):  # 기준노드, 이동
    if node == end: # 도착
        print(move) # 출력 후 프로그램 종료
        exit(0)
    for i in family[node]:
        if not visited[i]:  # 방문하지 않았다면
            visited[i] = True
            dfs(i, move + 1)


dfs(start, 0)
print(-1) # 탈출한 경우(못찾은 경우) -1 출력

 

 

풀이

- 조건에 따라 노드를 입력받고 시작노드를 기점으로 DFS를 전개해 나간다.

- 연결된 노드끼리 탐색이 완료되었는데도 찾지 못한경우 DFS를 탈출해 -1를 출력하는 반면 도중에 찾았다면 해당 노드값을 출력한 후 exit(0)으로 해당 프로그램을 종료하는 방식으로 문제를 풀이했다.

 

 

 

알게된 점

- 앞서 풀었던 문제(11725번 https://www.acmicpc.net/problem/11725)의 복습겸 풀었던 문제다.

 

 

참고 사이트

-