[백준] 1976 여행 가자 (파이썬)

골드 Ⅳ

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

1976번: 여행 가자

 

📄 문제

• 한국에는 도시가 N개 있고
• 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다.
• 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자.
• 중간에 다른 도시를 경유해서 여행을 할 수도 있다.
• 같은 도시를 여러 번 방문하는 것도 가능하다.

 

예를 들어,

도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고,

동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

 

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오.

 

---

💡 아이디어

• 두 도시 사이의 길이 주어지고, 여행 경로를 파악하는 문제이므로 그래프 탐색을 시행한다.
• 같은 도시를 여러 번 방문할 수 있다.
  • 각 여행지가 방문 순서에 관계없이 연결만 되어있으면 여행 경로대로 방문 가능하다.
  • 즉, 여행 도시 중 한 도시를 시작으로 모든 여행지에 방문 가능한지만 체크해 주면 된다.

• 즉, 각 여행지들이 연결되어 있는지만 확인하면 된다.
• 따라서, DFS 또는 BFS탐색을 시행한다.
• 여행지를 모두 방문했는지 확인하고 결과에 따라 'YES',  'NO'를 출력해 준다.

 

📝 문제 풀이 (Code)

BFS를 활용한 코드 ( 실행시간 48 ms, 메모리 31256 KB )

import sys
input = sys.stdin.readline

def bfs(v):
	# 방문한 여행지 저장
    check = set()
    # 각 도시의 방문체크 여부 저장
    visited = [0] * n
	
    stack = [v]
    # 방문 체크
    visited[v] = 1

    while stack:
        v = stack.pop()
        # 여행지이면 check에 저장
        if v+1 in set_plan:
            check.add(v+1)
            
        # 모든 여행지를 방문했으면 'YES' 반환
        if not set_plan-check:
            return 'YES'

        for w in graph[v]:
            if visited[w] == 0:
            	# 방문체크
                visited[w] = 1
                stack.append(w)
    # 모든 여행지가 이어져있지 않으면 'NO' 반환         
    return 'NO'


# 도시의 수
n = int(input())
# 여행 계획에 속한 도시들의 수
m = int(input())
# 연결 도시 저장
graph = [[] for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j]:
            graph[i].append(j)
            graph[j].append(i)

# 같은 도시를 여러 번 방문하는 것도 가능하므로
# 출발지를 시작으로 순서에 관계없이 각 여행지가 방문 가능한지만 체크
plan = list(map(int, input().split()))
set_plan = set(plan)

print(bfs(plan[0]-1))

---

DFS를 활용한 코드

import sys
input = sys.stdin.readline

def dfs(v):
    global check, visited
    # 방문 체크
    visited[v] = 1
    # 여행지이면 check에 저장
    if v+1 in set_plan:
        check.add(v+1)
	# 연결된 도시 탐색
    for w in graph[v]:
        if visited[w] == 0:
            dfs(w)


# 도시의 수
n = int(input())
# 여행 계획에 속한 도시들의 수
m = int(input())
# 연결 도시 저장
graph = [[] for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j]:
            graph[i].append(j)
            graph[j].append(i)

# 같은 도시를 여러 번 방문하는 것도 가능
# 출발지를 시작으로 순서에 관계없이 각 여행지를 방문 가능한지만 체크
plan = list(map(int, input().split()))
set_plan = set(plan)
# 방문체크 저장
visited = [0]*n
# 방문한 여행지 저장
check = set()
# 출발지를 시작으로 연결된 도시 탐색
dfs(plan[0]-1)

if set_plan-check:
    print('NO')
else:
    print('YES')