boj)13023 - ABCDE
2020. 10. 29. 15:44ㆍPS/boj
import java.util.*;
class Edge {
int from, to;
Edge(int from, int to) {
this.from = from;
this.to = to;
}
}
public class boj_13023{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 사람의 수
int m = sc.nextInt(); // 관계의 수
boolean[][] a = new boolean[n][n]; // 인접행렬
ArrayList<Integer>[] g = (ArrayList<Integer>[]) new ArrayList[n]; // 인접리스트
ArrayList<Edge> edges = new ArrayList<Edge>(); // 간접리스트
for (int i=0; i<n; i++) { // 인접리스트 배열 초기화
g[i] = new ArrayList<Integer>();
}
for (int i=0; i<m; i++) { // 그래프 그리기
int from = sc.nextInt();
int to = sc.nextInt();
edges.add(new Edge(from, to)); // 간접리스트에 표시
edges.add(new Edge(to, from));
a[from][to] = a[to][from] = true; // 인접행렬 표시
g[from].add(to); // 인접리스트 표시
g[to].add(from);
}
m *= 2; // 양방향 관계로 표시했으니 2배 해서 돌아야함
for (int i=0; i<m; i++) {
for (int j=0; j<m; j++) {
int A = edges.get(i).from; // i
int B = edges.get(i).to;
int C = edges.get(j).from; // j
int D = edges.get(j).to;
if (A == B || A == C || A == D || B == C || B == D || C == D) {
continue; // 같은 값 제외
}
if (!a[B][C]) continue; // B와 C의 관계 체크
for (int E : g[D]) { // D의 인접리스트를 돌며 같은 값이 없으면 연결된것이 맞음
if (A == E || B == E || C == E || D == E) {
continue;
}
System.out.println(1);
System.exit(0);
}
}
}
System.out.println(0);
}
}
- 인접행렬, 인접리스트, 간접리스트 를 사용
- 대부분의 경우는 인접리스트를 사용한다 -> 한 정점에 연결된 간선을 탐색하는 효율적인 측면에서 인접행렬보다 좋음
'PS > boj' 카테고리의 다른 글
boj)5014 - 스타트링크 (0) | 2020.11.02 |
---|---|
boj)2146 - 다리 만들기 (0) | 2020.11.02 |
boj)2206 - 벽 부수고 이동하기 (0) | 2020.10.24 |
boj)2573 - 빙산 (0) | 2020.10.24 |
boj)1629 - 곱셈 (0) | 2020.10.23 |