Chap 18. 그래프이론 - Q41. 여행 계획

@mildsalmon·2021-11-29 10:46

1. 여행 계획

난이도
- 중
풀이 시간
- 40분
시간 제한
- 1초
메모리 제한
- 128MB

A. 📜 문제

한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1~N번까지의 번호로 구분된다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미이다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 한다.

여행지의 개수와 여행지 간의 연결 정보가 주어졌을 떄, 한울이의 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하세요.

a. 예를 들면.

N = 5이고, 다음과 같이 도로의 정보가 주어졌다고 가정하자.

1번 여행지 - 2번 여행지
1번 여행지 - 4번 여행지
1번 여행지 - 5번 여행지
2번 여행지 - 3번 여행지
2번 여행지 - 4번 여행지

만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3 번이라고 해보자. 이 경우 2번 -> 3번 -> 2번 -> 4번 -> 2번 -> 3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있다.

b. 입력 조건

첫째 줄에 여행지의 수 N과 여행 계획에 속한 도시의 수 M이 주어진다.
- 1 <= N, M <= 500
다음 N개의 줄에 걸쳐 N * N 행렬을 통해 임의의 두 여행지가 서로 연결되어 있는지의 여부가 주어진다. 그 값이 1이라면 서로 연결되었다는 의미이며, 0이라면 서로 연결되어 있지 않다는 의미이다.
마지막 줄에 한울이의 여행 계획에 포함된 여행지의 번호들이 주어지며 공백으로 구분한다.

c. 출력 조건

첫째 줄에 한울이의 여행 계획이 가능하다면 YES, 불가능하다면 NO를 출력한다.

d. 테스트 케이스

입력 예시

출력 예시
```
YES
```

B. 💡 내 답안

a. 😊 1차 시도 (성공)


"""
Date    : 2021.11.26
Update  : 2021.11.26
Source  : Q41_여행 계획.py
Purpose : union-find 알고리즘으로 여행 계획이 가능한지를 판단한다.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# 부모노드 찾기
def find_parent(array, x):
    if array[x] != x:
        array[x] = find_parent(array, array[x])
    return array[x]

# 부모노드 합치기
def union_parent(array, a, b):
    a = find_parent(array, a)
    b = find_parent(array, b)

    if a > b:
        array[a] = b
    elif b > a:
        array[b] = a

# 여행 계획이 가능한지 확인
def check_plan(plan, parent):
    save_point = find_parent(parent, plan[0])

    for i in range(1, len(plan)):
        if find_parent(parent, i) != save_point:
            return "NO"
    return "YES"

# n = 여행지의 수, m = 여행 계획에 속한 도시의 수
n, m = list(map(int, input().split()))
graph = [[] for i in range(n)]

# 부모 노드
parent = [i for i in range(n)]

for i in range(n):
    temp = list(map(int, input().split()))

    # A지역에서 B지역으로 갈 수 있는 경우를 인접리스트 형식으로 저장
    for j in range(len(temp)):
        if temp[j] == 1:
            graph[i].append(j)

# 인접리스트를 순차적으로 접근하면서, 부모 노드가 다르다면, union
for i in range(len(graph)):
    for j in graph[i]:
        if find_parent(parent, j) != find_parent(parent, i):
            union_parent(parent, i, j)

plan = list(map(int, input().split()))

print(check_plan(plan, parent))

b. 😊 2차 시도 (성공) / 코드 최적화


"""
Date    : 2021.11.26
Update  : 2021.11.26
Source  : Q41_여행 계획.py
Purpose : union-find 알고리즘으로 여행 계획이 가능한지를 판단한다.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# 부모노드 찾기
def find_parent(array, x):
    if array[x] != x:
        array[x] = find_parent(array, array[x])
    return array[x]

# 부모노드 합치기
def union_parent(array, a, b):
    a = find_parent(array, a)
    b = find_parent(array, b)

    if a > b:
        array[a] = b
    elif b > a:
        array[b] = a

# 여행 계획이 가능한지 확인
def check_plan(plan, parent):
    save_point = find_parent(parent, plan[0])

    for i in range(1, len(plan)):
        if find_parent(parent, i) != save_point:
            return "NO"
    return "YES"

# n = 여행지의 수, m = 여행 계획에 속한 도시의 수
n, m = list(map(int, input().split()))

# 부모 노드
parent = [i for i in range(n)]

for i in range(n):
    temp = list(map(int, input().split()))

    for j in range(len(temp)):
        # A지역에서 B지역으로 갈 수 있는 경우
        if temp[j] == 1:
            # 부모 노드가 다르다면, union
            union_parent(parent, i, j)

plan = list(map(int, input().split()))

print(check_plan(plan, parent))