[Python/BOJ] 백준 1976 여행가자_유니온파인드

🐾 20220923

 

 

처음 DFS로 풀었다가 recursion Error로 까였다.

이렇게 생긴문제는 유니온파인드를 꼭 생각해서 풀어야겠다. 

 

 

 

간단하게 유니온 파인드를 정리해서 포스팅 해봤다. 

https://what-am-i.tistory.com/371?category=1000199 

[python]유니온파인드 알고리즘_이것도 알아야해?

 

 

 

---

 

 

 

1. 입력받은 도시의 연결 여부를 이용해 서로소 집합을 만든다. 

1-2. UNION - 부모 노드를 구해 비교한다. 다르면 동일하도록 만든다. 

1-3. FIND  - 부모노드를 찾는다. 

2. 여행경로를 돌면서 같은 서로소 집합에 있는지 확인한다. (부모노드가 동일한지 확인)

 

 

 

 

코드 : 

def find(target) :
    # 내가 부모노드라면 나를 반환 
    if target == parent[target] :
        return target 
    # 재귀적으로 부모노드를 찾음 
    # 내 부모님으로 설정 
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b) :
    a = find(a)
    b = find(b)
    # 다른 집합이면 union하기 
    if a!= b : parent[a] = b 

if __name__=="__main__" :
    n = int(input())
    m = int(input())
    mp = [list(map(int,input().split()))for _ in range(n)]
    parent = [x for x in range(n+1)]
    
    # 여행 경로 
    load = list(map(int,input().split()))
    

    for i in range(n) :
        for j in range(n) :
            # i에서 j로 갈 수 있다면 집합으로 연결 
            if mp[i][j] :
                union(i+1,j+1)
    
    ans = "YES"
    beforeCity = 0
    
    for idx,city in enumerate(load) :
        # 해당 도시의 부모노드를 findCity로 저장 
        findCity = find(city)
        
        # 출발지라면 
        if not idx :
            # 부모도시를 이전 도시로 
            beforeCity = findCity
            continue 
        # 이전 도시와 찾은 도시의 부모노드가 다르다면 
        if beforeCity != findCity :
            ans = "NO"
            break
        # 같은 집합에 있다면 
        beforeCity = findCity
    print(ans)

 

 

 

복습하면서 만들었다. 

다른 코드 : 

def union(a,b) :
    a = find(a)
    b = find(b)
    if a > b :
        parent[a] = b 
    elif a < b :
        parent[b] = a
        
def find(x) :
    if x!=parent[x] :
    	# 경로압축
        parent[x] = find(parent[x])
    return parent[x]
        
        
if __name__=="__main__" :
    n = int(input())
    m = int(input())
    mp = [list(map(int,input().split())) for _ in range(n)]
    parent = [0]*(n+1)
    
    for i in range(1,n+1) :
        parent[i] = i 
    travel = list(map(int,input().split()))
    
    for i in range(n) :
        for j in range(n) :
            if mp[i][j] :
                union(i+1,j+1)
    
    isok = True 
    for i in range(1,len(travel)) :
        if  parent[travel[i]]!= parent[travel[i-1]] :
            isok = False 
            break
    print("YES" if isok else "NO")

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://dailymapins.tistory.com/143

[백준/1976/파이썬] 여행 가자!