백준 13023번 ABCDE
문제
나의 풀이
import java.util.*;
public class Main {
static class Edge {
int from, to;
Edge(int from, int to) {
this.from = from;
this.to = to;
}
}
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;
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) { // A->B, C->D 확인
continue;
}
if(!a[B][C]) { // B->C 확인
continue;
}
for(int E : g[D]) { // D->E 확인
if(A == E || B == E || C == E || D == E) {
continue;
}
System.out.println(1);
System.exit(0);
}
}
}
System.out.println(0);
}
}인접행렬, 인접리스트, 간선리스트를 생성한다.
간선리스트를 통해 A->B, C->D를 찾는다.
그런 다음 인접행렬에서 B->C가 있는지 찾고
인접리스트를 이용해 D->E가 있는지 찾는다.
다 찾은 경우에는 1을 리턴해주면 된다.
결과
백준 1260번 DFS와 BFS
문제
나의 풀이
import java.util.*;
public class Main {
static ArrayList<Integer>[] a;
static boolean[] check;
public static void dfs(int x) {
if(check[x]) {
return;
}
check[x] = true;
System.out.print(x + " ");
for(int y : a[x]) {
if(check[y] == false) {
dfs(y);
}
}
}
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
check[start] = true;
while(!q.isEmpty()) {
int x = q.poll();
System.out.print(x + " ");
for(int y : a[x]) {
if(check[y] == false) {
check[y] = true;
q.add(y);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int start = sc.nextInt();
a = (ArrayList<Integer>[]) new ArrayList[n + 1];
for(int i = 1; i <= n; i++) {
a[i] = new ArrayList<Integer>();
}
for(int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
a[u].add(v);
a[v].add(u);
}
for(int i = 1; i <= n; i++) {
Collections.sort(a[i]);
}
check = new boolean[n + 1];
dfs(start);
System.out.println();
check = new boolean[n + 1];
bfs(start);
System.out.println();
}
}인접 리스트를 이용하여 DFS와 BFS 알고리즘을 구현하였다.
결과
백준 11724번 연결 요소의 개수
문제
나의 풀이
import java.util.*;
public class Main {
public static void dfs(ArrayList<Integer>[] a, boolean[] check, int x) {
if(check[x]) {
return;
}
check[x] = true;
for(int y : a[x]) {
if(check[y] == false) {
dfs(a, check, y);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n + 1];
for(int i = 1; i <= n; i++) {
a[i] = new ArrayList<Integer>();
}
for(int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
a[u].add(v);
a[v].add(u);
}
boolean check[] = new boolean[n + 1];
int answer = 0;
for(int i = 1; i <= n; i++) {
if(check[i] == false) {
dfs(a, check, i);
answer += 1;
}
}
System.out.println(answer);
}
}나누어진 각각의 그래프를 연결 요소라고 한다.
인접리스트를 만들고, 각각의 시작점에 대해서 방문한 적이 없으면 dfs를 시작하고, dfs를 시작한다는 것은 새로운 연결요소가 추가된다는 것이므로 개수를 1 증가 시켜주게 구현하면 된다.
결과
백준 1707번 이분 그래프
문제
나의 풀이
import java.util.*;
public class Main {
public static boolean dfs(ArrayList<Integer>[] a, int[] group, int x, int c) {
group[x] = c;
for(int y : a[x]) {
if(group[y] == 0) { // 아직 방문하지 않았다면
if(dfs(a, group, y, 3 - c) == false) { // 이분 그래프가 아닌 경우
return false;
}
} else if(group[y] == group[x]) { // 이미 방문했었고, 현재 노드와 다음 노드의 그룹 번호가 같은 경우
return false; // 이분 그래프가 아님
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n + 1];
for(int i = 1; i <= n; i++) {
a[i] = new ArrayList<Integer>();
}
for(int i = 0 ; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
a[u].add(v);
a[v].add(u);
}
int group[] = new int[n + 1];
boolean flag = true;
for(int i = 1; i <= n; i++) {
if(group[i] == 0) {
if(dfs(a, group, i, 1) == false) { // 그룹 번호 1번으로
flag = false;
}
}
}
if(flag) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}그래프를 A와 B로 나눌 수 있으면 이분 그래프라고 한다.
A에 포함되어 있는 정점끼리 연결된 간선이 없고, B에 포함되어 있는 정점끼리 연결된 간섬이 없어야 한다. 또한, 모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에 있어야 한다.
이 원리를 이용하여 dfs를 구현하는데 이분 그래프이면 true를 리턴하고 아니면 false를 리턴하도록 구현하여 탐색하면서 바로 판별할 수 있도록 한다.
판별하는 조건은 다음 정점의 그룹 번호와 현재 노드의 그룹 번호가 같으면 이분 그래프가 아니므로 false를 리턴하게 한다.
결과
가보자고