백준 1976 여행가자 문제풀이

문제 

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

1976번: 여행 가자

 

 

문제 접근 방식

도시 간 연결 관계가 주어지고 해당 그래프에서 특정 경로로 여행이 가능한지 판단하는 문제이다. 여행의 경우 같은 경로를 여러 번 방문할 수 있으며, 중간에 다른 도시를 갈 수 있다는 조건이 주어졌다. 이러한 조건 때문에 연결만 되어 있으면 해당 경로로 여행을 할 수 있다는 것을 알 수 있다. 즉, 주어진 여행지들이 서로 연결되어 있는지 판단하면 된다. 

 

서로 연결되어 있는 여행지들을 한 그룹으로 묶고, 같은 그룹에 속하는지 판별하는 문제이므로 유니온 파인드를 사용하여 문제를 풀었다.

 

 

시간 복잡도

그래프의 연결 관계가 행렬로 표현 되어서 O(n^2)이 걸리며, 여행 경로의 수 m 만큼 for 문을 돌려야하기 때문에 O(m) 의 시간이 걸린다. 전체적으로 O(n^2) 의 시간이 걸리고, n의 최댓값이 200 이하이므로 제한 시간내에 동작한다. 

 

코드

    def __init__(self,n):
        self.parents = [i for i in range(n + 1)]
        self.heights = [1 for _ in range(n + 1)]

    def find_parent(self,node):
        if self.parents[node]==node:
            return node
        self.parents[node]=self.find_parent(self.parents[node])
        return self.parents[node]

    def union(self,u,v):
        u=self.find_parent(u)
        v=self.find_parent(v)
        if u==v:
            return

        if self.heights[u]<self.heights[v]:
            u,v=v,u

        self.parents[v]=u

        if self.heights[u]==self.heights[v]:
            self.heights[u]+=1



if __name__=='__main__':
    n=int(input())
    m=int(input())

    union_find=UnionFind(n)

    for i in range(1,n+1):
        li=list(input().rstrip().split())
        li.insert(0,0)
        # 대칭이기 때문에 사선 기준 한 부분만 처리
        for j in range(i+1,n+1):
            if li[j]=='1':
                union_find.union(i,j)
    path=list(map(int,input().split()))

    answer=True    
    # 시작점의 root 를 구하고, 이후 경로들의 root와 비교한다.
    root=union_find.find_parent(path[0])
    for i in range(1,m):
        if union_find.find_parent(path[i])!=root:
            answer=False
            break

    print('YES') if answer==True else print('NO')

 

 

회고

여행 경로가 순서대로 주어져 있었지만 특정 조건으로 인해 여행지간 연결만 되어있으면 된다는 것을 알 수 있었다. 이를 통해 같은 그룹내에 존재하는지만 알면 되었기에 유니온 파인드를 사용하여 문제를 풀 수 있었다.