[백준] 1976 여행 가자

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

여행 계획의 중간에 다른 경로를 지나쳐도 상관 없이, 도시들을 방문할 수 있는지 여부만 판별하면 되었습니다.

DFS를 이용하여 여행 계획의 첫 도시를 출발점으로 하여 이동 가능한 모든 도시들을 탐색하였고, 계획의 도시들을 방문 가능한지 여부를 판별하였습니다.

2) 알고리즘

• DFS

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(start):
    stack = [start]                         # 첫 도시 출발점

    while stack:
        node = stack.pop()
        if not visited[node]:               
            visited[node] = 1               # 해당 도시 여행 가능
            for next in range(N):           # 해당 도시와 연결된 도시들 탐색
                if linked[node][next]:
                    stack.append(next)      # 연결된 다음 도시 여행

N = int(sys.stdin.readline())                                               # 도시의 수
M = int(sys.stdin.readline())                                               # 여행 계획 도시 수
linked = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]   # 도시들 간 연결 정보
want = list(map(int, sys.stdin.readline().split()))                         # 여행 계획

visited = [0] * N               # 도시 방문 가능 여부

solution(want[0]-1)             # 여행 계획의 첫 도시를 출발점으로 탐색

for w in want:
    if not visited[w-1]:        # 여행 계획에 있는 도시를 방문 가능한 경로가 없다면
        print('NO')             # NO 출력
        break
else:                           # 원하는 모든 도시 방문 가능하다면
    print('YES')                # YES 출력

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다