(JAVA) 백준 1976번 : 여행 가자

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

1976번: 여행 가자

 

 

Disjoint - Set 알고리즘 분류 문제인데

 

일반적인 방법으로 풀었다.

 

 

두 가지 전부 작성하겠다.

 

 

우선, 이 문제의 중점은

 

"경로 중복 가능하고, 이전 경로를 되돌아갈 수 있다."

 

는 것이다.

 

 

기존의 그래프 문제(특히, 다익스트라 같은) 들은 대부분 중복된 경로를 허용하지 않는다.

 

그렇기때문에 다른 알고리즘을 사용하는 것이고.

 

 

하지만 여기서는 반대로 가능하기 때문에

 

Disjoint - Set도 가능하다.

 

 

우선 제가 푼 첫 번째 방법은

 

"해당 지점에 도착한 적이 있으면 무조건 방문할 수 있다."

 

를 활용했다.

 

 

 

그렇기 때문에 해당 지점에서 출발하는 모든 경우의 수를 구해 방문 체크를 한다.

당연히 boolean 배열로 중복 방문을 제거한다.

*** 안그러면 두 점만 왔다갔다 할 수 있다..

 

다음, 입력받은 경로를 하나씩 까보며

 

 

방문 X(False)가 있으면 바로 불가능

하나라도 False가 없으면(전부 True) 가능

 

 

으로 정답을 얻을 수 있다.

 

쉽게 풀 수 있다.

 

 

 

그럼 두 번째

Disjoint - Set 은 어떻게 사용했나?

*** 참고로 위 첫 번째 방법과 시간과 용량은 비슷했다.

 

 

두 지점을 입력받으면

 

  1)  두 지점을 Union을 한다.

*** 이 때, 두 번 하는 것을 방지해야한다. 즉, (2, 3) 과 (3, 2) 를 입력받기 때문에 하나만 Union할 수 있도록 해야함

 

  2)  모든 경로의 Find() 값이 같으면 전부 같은 경로선상(동일선상)에 있다는 뜻이므로 정답

       하나라도 다르면 같은 경로선상이 아니므로 오답

 

 

 

쉽다.

 

쉬운데 아직은 Union - Find 사용 방법을 잘 모르겠다.

 

응용할 수 있는 범위가 넓어서 그런가?

 

 

 

 

따라서, 별도 매커니즘은 작성하지 않겠습니다!

 

소스코드 참고해주세요!

 

감사합니다.

 

소스코드

---