[Baekjoon Online Judge] 백준 1976번 여행 가자(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1976번 여행 가자

(Python)

(글쓴날 : 2020.05.16)

 

---

* Baekjoon Online Judge, 백준 1976번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1976번 여행 가자

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

---

2) 풀이 과정

* 시간 복잡도 : O(α(m), α : 아커만 함수)

 

N개의 도시와 여행 계획에 속한 M개의 도시가 주어지고, N * N 행렬을 통해 임의의 두 도시가 연결되어 있는지에 관한 정보가 주어질 때, 여행 계획이 가능한지 구하는 문제입니다.

 

저의 경우, 유니온 파인드를 적용하였으며, Python을 사용했습니다.

먼저, find() 함수와 union() 함수를 구현한 후, N * N 행렬을 통해 얻은 정보를 토대로 union() 함수를 호출하여 이어진 도시들을 집합화하였습니다.

(N * N 행렬의 행 인덱스가 기준 도시이고, 열 인덱스가 기준 도시와 연결되어 있는 도시들의 정보입니다.)

그 후, 최종적으로 여행 계획상의 도시들을 find() 함수로 탐색해 여행 계획이 가능한지 확인하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def find(target):
    if target == citys[target]:
        return target
    citys[target] = find(citys[target])
    return citys[target]
 
 
def union(A, B):
    A = find(A)
    B = find(B)
 
    if A < B:
        citys[B] = A
    else:
        citys[A] = B
 
 
N = int(input())
M = int(input())
citys = [ i for i in range(N + 1)]
 
for i in range(N):
    connectedCity = list(map(int, input().split()))
 
    for j in range(N):
        if connectedCity[j]:
            union(i + 1, j + 1)
 
plannedCities = list(map(int, input().split()))
 
isPossible = "YES"
beforeFindCity = 0
 
for i, city in enumerate(plannedCities):
    findCity = find(city)
    if not i:
        beforeFindCity = findCity
        continue
    if beforeFindCity != find(city):
        isPossible = "NO"
        break
    beforeFindCity = findCity
 
print(isPossible)

---