백준 1976 여행 가자 파이썬 풀이

난이도 : 골드4

풀이일 : 2404173

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

1976번: 여행 가자

---

문제 캡쳐

---

아이디어

• 연결되어 있지 않은 도시가 있는지 확인하는 문제이므로, union-find 알고리즘을 통해 연결 여부를 확인한다.
• 여행하고자 하는 도시들에 대해 연결상태를 확인하고 연결되지 않은 도시가 있는 경우, NO를 출력하고 확인을 중단한다.
• 여행하고자 하는 모든 도시가 연결되어 있어 중간에 중단되지 않은 경우에는 YES를 출력한다.

---

전체 풀이코드

import sys


# 부모를 거슬러 올라가 루트 탐색
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


# 두 수의 루트 탐색 후 연결
def union(x, y):
    x, y = find(x), find(y)
    if x > y:
        x, y = y, x
    parent[y] = x
    return


N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
parent = [i for i in range(N + 1)]  # 초기 설정

for i in range(N):
    # 연결 정보 리스트
    loads = list(map(int, sys.stdin.readline().split()))
    # 각 도시와 연결되어 있다면 union 함수로 연결
    for j in range(N):
        if loads[j]:
            union(i + 1, j + 1)

route = list(map(int, sys.stdin.readline().split()))  # 여행할 도시들
temp = parent[route[0]]  # 여행 첫 도시의 부모
for city in route:
    # 부모가 다른 도시는 연결되지 않은 도시
    if parent[city] != temp:
        print('NO')
        break
else:  # 모든 도시가 연결되어 있는 경우
    print('YES')

---

상세 풀이코드

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
parent = [i for i in range(N + 1)]  # 초기 설정

for i in range(N):
    # 연결 정보 리스트
    loads = list(map(int, sys.stdin.readline().split()))
    # 각 도시와 연결되어 있다면 union 함수로 연결
    for j in range(N):
        if loads[j]:
            union(i + 1, j + 1)

• 초기 입력을 받는 부분이다.
• parent : 각 인덱스를 넣은 배열을 만들고, 연결 시 이 배열을 바꾸어 연결 여부를 검사한다.
• for i 반복문 : 각 도시와 연결된 도시 정보를 입력받는다.
• for j 반복문 : i 도시와 다른 모든 도시들의 번호로, i 도시와 연결된 도시는 union 함수를 실행해준다.

 

route = list(map(int, sys.stdin.readline().split()))  # 여행할 도시들
temp = parent[route[0]]  # 여행 첫 도시의 부모
for city in route:
    # 부모가 다른 도시는 연결되지 않은 도시
    if parent[city] != temp:
        print('NO')
        break
else:  # 모든 도시가 연결되어 있는 경우
    print('YES')

• route : 여행을 원하는 경로 정보를 저장한다.
• temp : 여행을 원하는 모든 도시들이 연결되어 있는지 검사하기 위해, 임의로 맨 처음 도시의 parent를 temp로 설정한다.
• for 반복문 : 여행을 원하는 모든 도시에 대해 반복한다.
  • 만약, 도시의 parent가 temp와 같지 않다면, 연결되지 않은 도시이므로 NO를 출력하고 반복문을 종료한다.
  • 반복문이 끝날 때까지 연결되지 않은 도시가 없어 중단되지 않았다면, YES를 출력한다.