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

- Author: @mildsalmon
- Published: 2021-11-29
- Updated: 2021-11-29
- Source: http://blex.me/@mildsalmon/chap-18-%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-q41-%EC%97%AC%ED%96%89-%EA%B3%84%ED%9A%8D
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, find, union

---

# 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. 테스트 케이스

- 입력 예시

	```

	5 4
	0 1 0 1 1
	1 0 1 1 0
	0 1 0 0 0
	1 1 0 0 0
	1 0 0 0 0
	2 3 4 3

	```

- 출력 예시

	```

	YES

	```
	
### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

"""
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차 시도 (성공) / 코드 최적화

```python

"""
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))

```

##### a. 🙄 회고

> 내 풀이

- union-find라는 느낌이 왔다.
	- 코드를 작성하는 중간중간 union-find를 어떤 방식으로 작성해야했는지 확신이 들지 않았다. (~~까먹었다.~~)

> 반성

- 다행히, 다 잘 작성했다. 그러나 코드를 조금 난잡하게 작성했다.

> 결론

- 복습해야지..

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2021/11/29//2021_11_29_10_0jm5uctmMF36tKLjkEvG.jpg)

![](https://static.blex.me/images/content/2021/11/29//2021_11_29_10_Uga4ofdj6IhgrXQp2Z6q.jpg)

##### a. 책 답안

[python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/18/1.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년