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

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차 시도 (성공)

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

a. 🙄 회고

내 풀이

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

반성

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

결론

  • 복습해야지..

C. 🧐 문제 해설

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

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

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

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.