[백준] 13023번 ABCDE 문제 그래프로 풀어보기
1. 문제
1) 링크
2) 문제
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.
3) 입력
첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
4) 출력
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
더 자세한 문제의 조건을 보고 싶다면 위의 링크를 클릭해보자
2. 풀이
우선 이 문제는 그래프의 다양한 표현방식을 이용하여서 풀 수 있는 문제이다.
https://www.programmingstory.com/2024/02/blog-post_16.html
전의 포스트에서 그래프의 다양한 표현방식에 대해서 이야기를 했는데,
여기서 설명한 간선리스트, 인접행렬, 인접리스트 세 가지 방식을 이 문제에서 모두 다 활용할 수 있다.
class Edge{
int from, to;
Edge(int from, int to){
this.from=from;
this.to=to;
}
}먼저 나는 간선을 표현하기 위해서 Edge라는 새로운 class를 하나 더 만들어주었다. from, to 를 instance로 가지는 class이다. 사실 알고리즘 문제를 자바로 풀 때 class를 새로 만드는 경우가 많이 없는데 이 문제는 새로운 class를 만들어서 풀면 훨씬 효과적인 문제라 신선했던 것 같다.
boolean [][]a=new boolean[n][n];
ArrayList<Integer>[] g=(ArrayList<Integer>[] )new ArrayList[n];
ArrayList<Edge> edges=new ArrayList<>();위의 세 가지가 이 문제를 풀기 위한 준비물이라고 할 수 있다.
첫번째 [][]a 의 배열은 인접행렬을 저장하기 위한 공간이라고 할 수 있다.
두번째 ArrayList<Integer>[] g는 인접리스트를 저장하기 위한 배열이다. (ArrayList의 배열이라는 점이 신기한 점이다)
마지막으로 ArrayList<Edge> edges는 가능한 간선을 저장하기 위한 ArrayList이다.
그리고 문제에서 가능한 경우를 입력을 받은 뒤,
int from=sc.nextInt();
int to=sc.nextInt();
edges.add(new Edge(from, to));
edges.add(new Edge(to, from));
g[to].add(from);
g[from].add(to);
a[to][from]=a[from][to]=true;이런식으로 추가를 하는 것이 필요하다. 먼저 간선을 저장하기 위해서 새로운 Edge 객체를 만든 뒤 이를 저장하고 있는 ArrayList edges에다가 추가해준다. 이것은 양방향 그래프이기 때문에 from과 to를 바꿔서 두 번 총 저장해준다.
다음으로 인접리스트에다가도 양방향으로 추가를 해준다. 또한 인접행렬은 boolean으로 만들었기 때문에 이 또한 양방향으로 해당 값을 true로 만들어준다.
그렇다면 이 문제를 어떤 방식으로 풀면 좋을지에 대해서 고민해보자.
먼저 간선을 저장해 놓은 배열이 있기 때문에 그 배열에서 두 가지 Edge 객체를 가져오자.
A-B-C-D-E가 가능한 경우를 찾아야 할 것이기 때문에, 먼저
우리는 A<->B 와 C<->D가 가능한지를 간선리스트로부터 찾을 수 있다. 이중 for문을 돌면서 두 개의 (from, to) set를 찾는 느낌인 것이다. 그렇다면 이는 이미 간선리스트에서 가져온 것이기 때문에 A,B 그리고 C,D가 각각 서로 친구인지는 살펴볼 필요가 없고 A, B, C, D 중에서 중복인 값이 있는지만 살펴보면 되는것이다.
없다면 우선 일차적으로 우리는 A와 B가 친구이고 C와 D가 친구인 쌍을 찾아낸 것이다.
그렇다면 이제 B와 C가 친구인지를 판단해야 하는데 앞에서 이런 경우에 효과적으로 찾아낼 수 있는 방법은 인접행렬을 사용하는 것이라고 했다. 따라서 간단하게 a[B][C]가 true를 만족하는지만 판단하면 된다.
만약 a[B][C]의 값까지 true가 된다면 현재 우리는 A-B-C-D-E 중에서 A-B-C-D까지 만족시킨 쌍을 찾은 것이다.
그러면 마지막으로 D-E가 연결되어 있으면 좋은데 여기서 우리는 인접리스트를 사용할 것이다.
인접리스트를 저장해놓은 g[D] 를 for문으로 돌면서 확인을 하면 되는데, 여기 또한 인접리스트에 들어가 있다는 것은 이미 친구라는 뜻이므로 친구의 유무를 검사하는 것이 아니라, E가 A,B,C,D와 같은 사람이 아닌지를 검사해주는 것이다.
만약 같은 사람이 아니라면 E는 A,B,C,D가 아니면서 D와 친구이므로 최종적으로 A-B-C-D-E가 가능한 경우를 찾아낸 것이다.
이 모든 것을 코드로 옮기면,
import java.util.*;
class Edge{
int from, to;
Edge(int from, int to){
this.from=from;
this.to=to;
}
}
public class Main{
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<>();
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));
g[to].add(from);
g[from].add(to);
a[to][from]=a[from][to]=true;
}
m=m*2;
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
int A=edges.get(i).from;
int B=edges.get(i).to;
int C=edges.get(j).from;
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;
}
for (int E: g[D]){
if (A==E || B==E||C==E||D==E){
continue;
}
System.out.println(1);
System.exit(0);
}
}
}
System.out.println(0);
}
}이렇게 풀 수 있다.
경우를 찾았다면 System.exit(0)을 해서 exit하고 그 이외의 경우에는 0을 출력해주면 된다.
이 문제는 이런 방법 외에도 다른 방법을 사용해서 여러가지로 풀 수 있다.