Q41 여행 계획

domybest·2021년 4월 9일
0

실전 문제

목록 보기
3/34

문제 : 이것이 코딩테스트다 교재 Q41 실전문제..
풀이 코드

알고리즘

여행 계획이 가능하다는 것은 그 여행지들이 모두 연결 되어 있어야 한다. 반대로 여행 계획이 불가능 하다는 것은 연결 되지 않은 노드가 존재한다 즉, 서로소 집합으로 나눌 수 있다는 의미이다. 따라서 노드 연결성을 입력받아 union 연산을 진행하여 부모 테이블을 완성한 후에 여행 계획으로 주어진 노드의 집합 번호가 모두 같으면 YES, 아니면 NO를 출력하도록 하면 해결된다.
다만 노드 연결성을 확인할 때 양방향 특성을 이용하여 대각선 기준 절반만 확인할 수 있도록 반복문을 작성하는 것도 핵심이다.

profile
기억할 때 까지 반복!

0개의 댓글