1976 여행 가자 _pyth

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

1976번: 여행 가자

최근 푼 것 중 가장 열심히 풀었고 잘풀었는 듯...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

이번 문제는 Union-Find의 알고리즘을 찾아들어가서 푼 문제다.

하지만 문제를 보자말자 BFS나 DFS로 풀어도 똑같을 것 같다는 생각이 들어서 알면서도 풀어봤다.

결과는 그래프탐색이나 Union-Find이나 둘다 엄청 빠른속도로 풀렸다. 48ms 같은속도

 

그래프 탐색의 풀이

입력받은 이동가능한 지역 데이터를 그래프탐색을 한다.

이동가능한 지역을 탐색 후 저장한다.

여행계획의 경로를 이동가능한 지역과 포함여부를 비교해서 YES와 NO를 출력한다.

여행계획의 경로에 indexError를 막으려면 1을 빼줘야한다.

 

 

Union-Find의 풀이

https://portable-paper.tistory.com/entry/Union-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Find와 Union을 구현한다.

부모를 비교하는 함수도 추가로 구현했다.

부모를 비교하기전에 indexError를 막으려면 1을 빼줘야한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그래프 탐색 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

"""
1976 여행 가즈아!!!!
Union and Find?? BFS or DFS??

--BFS or DFS--
(i번째 j줄) 데이터로 BFS or DFS를 해서 이동가능한 지역을 탐색후 저장 -> area
여행계획의 경로를 set으로 저장후 area와 포함여부 비교

--Union and Find--

"""

#입력
N = int(input())
M = int(input())
connect = []
for _ in range(N):
    connect.append(list(map(int,input().split())))
plan = list(set(map(int,input().split())))
connectArea = []

#DFS
stack = [plan[0]-1]
visited = [False for i in range(N)]
visited[stack[0]] = True
connectArea.append(stack[0])

while stack:
    x = stack.pop()
    for i in range(N):
        if connect[x][i] and not visited[i]:
            stack.append(i)
            visited[i] = True
            connectArea.append(i)

for i in range(len(plan)):
    if plan[i]-1 not in connectArea:
        print("NO")
        break
else:
    print("YES")

30812KB  48ms

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Union-Find 코드

import sys
input = sys.stdin.readline

"""
1976 여행 가즈아!!!!
Union and Find?? BFS or DFS??

--BFS or DFS--
(i번째 j줄) 데이터로 BFS or DFS를 해서 이동가능한 지역을 탐색후 저장 -> area
여행계획의 경로를 set으로 저장후 area와 포함여부 비교

--Union and Find--
그대로 구현.
마지막줄은 -1해줘야함
"""

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
        return parent[x]
    return x

def union(x, y):
    a = find(x)
    b = find(y)
    if a < b: parent[b] = a
    else: parent[a] = b

def compareParent(arr):
    result = []
    for i in arr:
        result.append(find(i))
    if len(list(set(result))) == 1: return True
    else: return False

#plan의 값을 1 빼주기위해
def minus1(n):
    return n-1

#입력
N = int(input())
M = int(input())
parent = [i for i in range(N)]
for i in range(N):
    connect = list(map(int,input().split()))
    for j in range(N):
        if connect[j]:
            union(i, j)
plan = set(map(int,input().split()))
plan = map(minus1,plan)


#Union-Find
if compareParent(plan): print("YES")
else: print("NO")

30616KB  48ms