[이것이 코딩테스트다] 여행 계획

문제

• 1~N번까지의 N개의 여행 중 M개의 여행지를 여행하려고 한다.
  • 1 <= N, M <= 500
• 임의의 두 여행지는 도로로 연결되어 있고, 이 경우 양방향으로 이동이 가능하다.
• 한울이가 여행 계획을 세웠을 때, 이 여행 계획이 가능한지 여부를 판단하고자 한다.
  • 예) 여행 계획 : 2 -> 3-> 4 -> 3 
  • 모든 경우 다음 여행지로의 이동이 가능하다면 가능한 여행 계획이다.

 

풀이

• 유니온 파인드 문제
• 둘의 부모가 같다면 이동 가능한 여행지로 볼 수 있을 것이다.
• 시간 복잡도 : O( V + M)

 

# 부모 찾기
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a 
    else:
        parent[a] = b

# 입력 받기
N, M = map(int, input().split())
parent = [i for i in range(N+1)]    # 부모 테이블

# 연결된 여행지 정보
for i in range(N):
    link = list(map(int, input().split()))  # 연결 정보
    for j in range(N):
        if link[j] == 1:                    # 연결된 경우
            union_parent(parent, i+1, j+1)  # 합치기

places = list(map(int, input().split()))    # 여행 계획

# 모든 여행지의 부모가 같으면 여행 가능
p = find_parent(parent, places[0])          
answer = "YES"
for x in places[1:]:
    if p != find_parent(parent, x):
        answer = "NO"
        break

print(answer)

 

References

• 이것이 코딩테스트다 Q41