[알고리즘] 백준 > #1976. 여행 가자
😆😆
문제링크
풀이방법
백준 > #1717. 집합의 표현 문제랑 풀이방법이 98% 같은 문제입니다 ㅎㅎ
위 문제와 같이 집합합치기/같은집합여부 연산만으로 해결가능한 문제죠? 유니온파인드를 사용했습니다! 도시들 간의 연결 정보를 받고 "1"이면 두 도시를 merge하는 연산을 진행했습니다. 그리고 여행경로의 첫번째 도시의 루트를 저장해두고, 뒤따라오는 도시들의 루트를 find해 동일한 루트를 갖는지 확인했습니다! 쉬운문제네용
코드
import java.util.Scanner;
public class LetsGoTrip {
static final int ROOT = -1;
static int[] p;
static public void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] map = new int[n][n];
p = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) map[i][j] = sc.nextInt();
p[i] = ROOT;
}
for (int a = 0; a < n; a++) {
for (int b = 0; b < a; b++) if (map[a][b] == 1) merge(a, b);
}
int result = 1;
int commonRoot = find(sc.nextInt() - 1);
for (int i = 1; i < m; i++) {
if (find(sc.nextInt() - 1) != commonRoot) {
result = 0;
break;
}
}
System.out.print((result == 1) ? "YES" : "NO");
}
private static int find(int id) {
if (p[id] == ROOT) return id;
else {
p[id] = find(p[id]);
return p[id];
}
}
private static void merge(int idA, int idB) {
int aRoot = find(idA);
int bRoot = find(idB);
if (aRoot != bRoot) p[bRoot] = idA;
}
}
📚
Author And Source
이 문제에 관하여([알고리즘] 백준 > #1976. 여행 가자), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@cchloe2311/알고리즘-백준-1976.-여행-가자
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([알고리즘] 백준 > #1976. 여행 가자), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/알고리즘-백준-1976.-여행-가자저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)