학습용 공간

그래프의 정점의 집합을 둘로 분할하여,

각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때,

그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

dfs로 정점들을 탐색하며 간선으로 연결된 정점들은 다른 집합에 속하도록 한다.

check[x] == 1 또는 2 // 집합 1 또는 2에 넣기 (0이면 방문 안한 정점)

 

입력 예제는 성공했지만 계속 4초에서 3초로 넘어가는 중에 실패처리가 나와서 의문이였는데

그래프가 2개 이상의 연결요소로 구성된 경우를 처리하지 않았기 때문이라는 것을 깨달았다.

(그래프의 모든 정점들이 연결되어 있지 않고 섬처럼 떨어져 있을 수도 있다는 것)

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접리스트로 그래프 구현
    static int[] check; // 각 정점의 방문여부와 소속 집합을 기록 (0:방문안함, 1:집합1, 2:집합2)

    static void dfs(int x, int prevGroup) {
        if (prevGroup == 1) check[x] = 2;
        else if (prevGroup == 2) check[x] = 1;
        for (int y : graph[x]) {
            if (check[y] == 0) { // 방문 안한 정점이면
                dfs(y, check[x]);
            }
        }
    }

    static String checkBipartite(int vertex) {
        for (int i=1;i<=vertex;i++) { // 모든 정점과 연결된 정점들에 대해 확인
            for (int x : graph[i]) { // (모든 간선을 확인)
                if (check[i] == check[x]) { // 간선으로 연결된 간선이 같은 집합에 속하면
                    return "NO"; // 이분 그래프가 아님
                }
            }
        }
        return "YES"; // 위 루프를 모두 통과하면 이분 그래프가 맞음
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt(); // 테스트 케이스 개수
        for (int i=0;i<cases;i++) {
            int n = sc.nextInt(); // 정점의 개수
            int m = sc.nextInt(); // 간선의 개수
            graph = (ArrayList<Integer>[]) new ArrayList[n+1]; // 정점의 개수만큼 리스트를 원소로 갖는 배열 생성
            for (int j=1;j<=n;j++){
                graph[j] = new ArrayList<Integer>(); // 각 정점마다 리스트 생성
            }
            for (int j=0;j<m;j++) { // 간선 저장
                int u = sc.nextInt();
                int v = sc.nextInt();
                graph[u].add(v);
                graph[v].add(u);
            }
            check = new int[n+1]; // 각 정점에 대한 방문 여부와 집합 기록 배열 생성
            // 그래프를 구성하는 연결요소가 2개 이상일 수도 있기 때문에
            // dfs 수행하고도 방문하지 않은 정점이 있는지 확인해야 함
            for (int j=1; j<=n; j++) {
                if (check[j] == 0) {
                    dfs(j, 1);
                }
            }
            System.out.println(checkBipartite(n));
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1707

그래프의 연결 요소를 확인하는 방법은

임의의 정점에서 DFS 또는 BFS 탐색을 수행한 후에도 

방문하지 않은 정점이 남아있다면, 

다른 연결요소가 있다는 특성을 이용한 것이다.

 

모든 정점들에 대하여 각 정점을 방문했는지 확인하고, 

방문하지 않은 정점이 있다면 연결요소의 개수를 1개 추가하고

해당 정점에서 다시 탐색을 수행한다.

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접 리스트로 그래프 구현
    static boolean[] check; // 정점 방문 여부 확인하는 배열

    static void dfs(int x) {
        if (check[x]) return; // 이미 방문한 정점이면 해당 정점에서는 탐색 안함
        check[x] = true; // 정점 방문 체크
        for (int y : graph[x]) {
            if (!check[y]) { // x와 연결된 정점 y를 방문하지 않았으면
                dfs(y); // 정점 y 방문해서 탐색 수행
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n = 정점의 개수
        int m = sc.nextInt(); // m = 간선의 개수
        // 그래프 구현
        graph = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1;i<=n;i++) graph[i] = new ArrayList<Integer>();
        for (int i=0;i<m;i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        boolean flag = true; // 모든 연결요소 확인했으면 true, 아니면 false
        int compNum = 0; // 연결 요소의 개수
        // 정점 방문 여부 초기화
        check = new boolean[n+1];
        for (int i=1;i<=n;i++) { // 모든 정점에 대해 반복문 돌림
            if (!check[i]) { // 방문 안한 정점이 있다는 것은 확인 안한 연결요소가 있다는 것
                compNum+=1; // 연결요소 수 추가
                dfs(i); // 해당 연결요소 탐색 수행
            }
        } // 모든 정점이 방문 처리되었으면 모든 연결요소를 확인한 것임
        // 확인된 연결요소의 개수 출력
        System.out.println(compNum);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/11724

리스트(그래프)의 원소(정점) 접근은 for each문을 사용하여 처리한다.

(for문과 get()메소드로 인덱스를 사용해 접근하는 것보다 빠르기 때문)

위의 이유에 대해서는 하단 링크 참고

https://starmk95.tistory.com/110 

 

JAVA) 리스트에는 for문 대신 for each 문을 사용하자

ArrayList 자료구조를 예시로 들어 설명하면 ArrayList.get(인덱스) 메소드를 실행하면 내부적으로 해당 인덱스를 찾기 위해 루프가 돌게 된다고 한다. 그렇기 때문에 리스트의 원소에 접근할 때, for ea

starmk95.tistory.com

인접 리스트를 사용해 그래프를 구현했고

DFS는 재귀, BFS는 Queue를 통해 구현했다.

import java.util.*;

public class Main {

    static ArrayList<Integer>[] graph; // 인접리스트 방식으로 그래프 저장
    static boolean[] check; // 정점 방문 여부를 확인하는 배열
    // 리스트(그래프)의 원소(정점) 접근은 for each문을 사용하여 처리
    // (for문과 get()메소드로 인덱스를 사용해 접근하는 것보다 빠르기 때문)

    static void dfs(int x) {
        if (check[x]) return; // 이미 방문한 적이 있는 정점이라면 해당 정점 탐색하지 않음
        check[x]= true; // 방문한 정점 체크
        System.out.print(x + " "); // 정점 방문하면 출력
        for (int y : graph[x]) { // 각 정점에 연결되어 있는 정점들 모두에 대해 확인 (리스트에도 for each문 적용 가능)
            if (!check[y]) { // 방문한 적이 없는 정점이라면
                dfs(y); // 해당 정점을 방문하고 그 정점에서 dfs 수행
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start); // 처음으로 bfs 탐색을 시작할 정점을 큐에 추가
        check[start] = true; // 정점 방문 체크
        while (!queue.isEmpty()) { // 큐가 비면 모든 탐색을 완료한 것임
            int x = queue.remove(); // bfs 탐색을 수행할 현재 정점
            System.out.print(x + " "); // 정점 방문하면 출력
            for (int y : graph[x]) { // bfs를 수행하는 정점에 연결된 모든 정점들 확인
                if (!check[y]) { // 정점을 방문하지 않았다면
                    queue.add(y); // 정점 방문
                    check[y] = true; // 정점 방문 체크
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();
        int start = sc.nextInt();
        graph = (ArrayList<Integer>[]) new ArrayList[v+1];
        for (int i=1;i<=v;i++) { // 각 배열의 원소(정점)에 대해 리스트 생성
            graph[i] = new ArrayList<Integer>();
        }
        // 각 배열의 원소는 각 정점에 해당한 정점들을 저장하는 리스트로 구성된다.
        for (int i=0;i<e;i++) {
            int temp1 = sc.nextInt();
            int temp2 = sc.nextInt();
            // 양 정점 모두에 add 해주어야 함 (undirected edge이기 때문)
            graph[temp1].add(temp2);
            graph[temp2].add(temp1);
        }
        // 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하는 조건을 충족하기 위한 정렬
        for (int i=1;i<=v;i++) Collections.sort(graph[i]);

        check = new boolean[v+1]; // dfs 수행 전에 정점 방문 여부 배열 초기화
        dfs(start);
        System.out.println();
        check = new boolean[v+1]; // bfs 수행 전에 정점 방문 여부 배열 초기화
        bfs(start);
        
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1260

ArrayList 자료구조를 예시로 들어 설명하면

 

ArrayList.get(인덱스) 메소드를 실행하면 내부적으로 해당 인덱스를 찾기 위해 루프가 돌게 된다고 한다.

그렇기 때문에 리스트의 원소에 접근할 때,

for each문을 사용하지 않고 for문을 사용하여 index를 이용해 get으로 접근하면

이중 루프를 사용한 것이 되어 O(n^2)의 시간이 걸리게 된다.

 

그러나 애초에 for each문을 사용하여 리스트의 원소에 접근하면 get() 메소드를 사용할 필요가 없으므로

루프를 한번만 사용한 것이 되어 O(n)의 시간이 걸린다.

 

// 리스트를 for문으로 접근할 경우
for (int i=0;i<ArrayList.size();i++) { // 외부 루프
	int num = ArrayList.get(i) // get() 메소드 내부적으로 실행되는 내부 루프
} // -> 가시적으로는 for문 루프 1번이지만 실제 동작으로 생각하면 이중 루프이다.

// 리스트를 for each문으로 접근할 경우
for (int x : ArrayList) { // 루프 1번
	int num = x;
} // get() 메소드를 사용하지 않고 리스트의 원소에 접근하기 때문에 for each문으로 인한 루프 1번만 사용된다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp;
        while ((temp = br.readLine()) != null) { // eof 처리
            int upper = 0;
            int lower = 0;
            int num = 0;
            int space = 0;
            for (int i=0;i<temp.length();i++){
                char c = temp.charAt(i);
                if (Character.isUpperCase(c)) upper+=1;
                else if (Character.isLowerCase(c)) lower+=1;
                else if (Character.isDigit(c)) num+=1;
                else if (Character.isSpaceChar(c)) space+=1;
            }
            System.out.printf("%d %d %d %d\n", lower, upper, num, space);
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/10820

문제가 쉬워보이는데 오답률이 높길래 의아해서 풀었다가 나도 틀려서 당황한 문제

문제의 요구사항(조건)을 잘 확인해야 한다는 것을 느낄 수 있는 문제였다.

 

문제의 포인트는 알맞는 자료형을 사용하는 것

 

문제에서 주어지는 4개의 자연수의 각 최대 값은 1,000,000

A와 B를 이어붙인 수는 10,000,001,000,000이 되는데, 이는 int 자료형의 범위를 넘어간다.

그러므로 long 자료형을 사용해서 A, B와 C, D가 이어진 수와 그 합을 처리해줘야한다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        String C = sc.next();
        String D = sc.next();

        String AB = A + B;
        String CD = C + D;

        long sum = Long.parseLong(AB) + Long.parseLong(CD);
        System.out.println(sum);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/10824

해당 문제를 해결하기 위해

괄호에 의한 우선 순위 뿐만 아니라

사칙연산의 연산자들 간의 우선 순위도 고려해야 한다.

(괄호) > *, / (곱셈, 나눗셈)  > +, - (덧셈, 뺄셈)

 

# 알고리즘

모든 수식의 입력들 처리할 때까지 반복

1. 입력이 피연산자(알파벳)이면

바로 출력문에 append()

2. 입력이 열린 괄호 "("이면

바로 출력문에 append()

3. 입력이 + 또는 - 이면 

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      a 또는 b 과정 끝나면 입력된 연산자 push

4. 입력이 * 또는 / 이면

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      c) 우선순위 낮은 연산자 + 또는 - 를 만나면 중지

      a 또는 b 또는 c 과정 끝나면 입력된 연산자 push

5. 입력이 닫힌 괄호 ")"이면

스택에서 열린 괄호 "("가 나올 때까지 pop()하고 append()

 

모든 수식의 입력들을 처리한 후에

스택에 남아있는 연산자가 있다면 모두 pop()하고 append()

 

완성된 출력문 출력

 

아래는 문제를 해결하는 코드이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        Scanner sc = new Scanner(System.in);
        String inorder = sc.next();
        String[] each = inorder.split("");
        StringBuilder sb = new StringBuilder();
        for (String x : each) {
            if (x.equals(")")) { // 닫힌 괄호가 들어오면 stack에 열린 괄호가 나올 때까지 pop하고 식에 append 해줌
                while (!stack.peek().equals("(")) {
                    sb.append(stack.pop());
                }
                stack.pop(); // "(" stack에서 제거
            } else if (x.equals("+") || x.equals("-")) {
                // +,-연산자가 들어올 때
                // stack이 비거나 열린 괄호가 나오거나
                // stack에 있는 우선 순위가 같은 +, - 연산자들은 append 해준다. (stack에는 열린 괄호와 연산자만 들어감)
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // 아니라면 stack이 빌때까지 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("*") || x.equals("/")) {
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // *, /보다 우선 순위가 낮은 +, - 연산자를 만나면 pop과 append 중지
                        else if (stack.peek().equals("+") || stack.peek().equals("-")) break;
                        // 아니라면 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("(")) {
                // 열린 괄호가 들어와도 stack에 넣어준다.
                stack.push(x);
            } else {
                // 피연산자가 들어오면 바로 append
                sb.append(x);
            }
        }
        // 반복문을 다 돌고도 stack에 남아있는 연산자가 있다면
        // -> 열림 괄호 없이 들어온 연산자가 있었을 경우 처리
        while (!stack.empty()) sb.append(stack.pop());

        System.out.print(sb);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1918

# 트리 : 사이클이 없는 연결 그래프

1. 사이클이 없다

2. 연결되어 있다.

3. 그래프이다.

 

트리의 정점의 개수 = V,

트리의 간선의 개수 = V-1

(정점이 N개, 간선이 N개면 사이클이 1개만 존재하게 된다.)

 

cf) 트리라고 무조건 루트가 존재하는 것은 아니다.

루트는 정하기에 따라 달라진다.

 

# 트리에서의 부모(parent), 자식(child), 단말 노드(leaf node)

위 예시에서 

루트 = 노드 1로 정의했을 때,

노드 1의 자식 = 노드 2, 노드 3

노드 2의 부모 = 노드 1

(루트 노드(노드 1)의 부모는 존재하지 않는다.)

해당 트리의 단말 노드 = 노드 4, 5, 6, 7

노드 2의 형제(sibling) 노드 = 노드 3

 

# 깊이(Depth) : 루트로부터 노드의 거리

깊이는 정의마다 값이 다른데 일반적으로

root의 깊이를 0으로 설정하느냐, 1로 설정하느냐에 따라 달라진다

ex) 노드 4의 깊이 = (전자면) 2, (후자면) 3

 

# 높이(Height) : 단말 노드로부터의 거리

높이 역시 단말노드의 높이를 0으로 하느냐 1로 하느냐에 따라 달라진다.

 

# 조상(Ancestor), 후손(Descendent)

위 개념의 가장 큰 특징을 자신을 포함한다는 것이다.

ex) 노드 4의 조상 = 노드 4, 노드 2, 노드 1

노드 3의 후손 = 노드 3, 노드 6, 노드 7

 

 

# 이진 트리 (Binary Tree) : 자식을 최대 2개만 갖는 트리

(위 트리 예시는 이진 트리의 예시이기도 하다.)

 

# 포화 이진 트리 (Full Binary Tree) : 모든 단말 노드에서의 깊이가 동일한 이진 트리

포화 이진 트리의 전체 노드의 개수 = (2^h)-1

(h = 트리의 최대 높이)

위 트리 예시는 포화 이진 트리의 예시이기도 하다.

(단말 노드인 노드 4, 5, 6, 7의 깊이가 모드 3)

# 완전 이진 트리 (Complete Binary Tree) : 마지막 level(깊이)에서 오른쪽 leaf 노드의 일부가 없어진 형태

아래는 완전 이진 트리의 예시들이다.

위 그림의 오른쪽 예시에서 노드 7이 추가되어 있다면, 해당 트리는 완전 이진 트리가 아니다.

 

 

# 트리의 구현

- 그래프 구현 방식으로 구현할 수 있다. (트리도 그래프의 일종이기 때문)

- root가 존재한다면, 트리만의 저장 방식을 사용할 수 있다.

1) 부모만 저장하는 방식 - Union Find에 사용

-> 모든 노드들의 부모를 배열에 저장하는 방식으로 구현한다.

(모든 노드는 부모 노드가 1개이고, 부모가 없는 노드는 root 노드 하나만 존재하기 때문에 사용가능한 방식이다.)

위 방식은 부모를 찾는것은 수월하지만 O(1)

자식을 찾는데는 O(노드개수) 만큼의 시간이 걸린다.

2) 완전 이진 트리 - Heap, Segment Tree 구현에 사용한다.

완전 이진 트리의 경우에는 배열을 사용하여 트리를 구현하는 것이 가능하다.

3) 그냥(일반) 이진 트리 

구조체 또는 클래스를 사용하여 구현한다.

 

# 트리의 탐색

트리를 탐색하는데에도 DFS/BFS 방식을 사용할 수 있다.

(트리도 그래프의 일종이기 때문이다.)

1. DFS - 출력 순서 3가지 (노드 방문 처리 시점에 따른 차이)

   1) pre-order

   2) in-order

   3) post-order

 

 

1) pre-order : 그래프의 DFS 방문 순서와 동일하다는 특징이 있다.

순서 :

노드 방문 ->

왼쪽 자식를 루트로 하는 서브 트리의 pre-order 출력 -> 

오른쪽 자식를 루트로 하는 서브 트리의 pre-order 출력

ex) A B D E C F G

2) in-order : Binary Searcj Tree의 삭제를 구현하는데 inorder successor가 사용된다는 특징이 있다.

순서 : 

왼쪽 자식를 루트로 하는 서브 트리의 in-order 출력 ->

노드 방문 ->

오른쪽 자식를 루트로 하는 서브 트리의 in-order 출력

ex) D B E A F C G

3) post-order : 자식의 노드의 정보를 이용하여 현재 노드에 정보를 저장할 때 사용하기 용이하다. (중요)

순서 :

왼쪽 자식를 루트로 하는 서브 트리의 post-order 출력 ->

오른쪽 자식를 루트로 하는 서브 트리의 post-order 출력 ->

노드 방문

ex) D E B F G C A

 

cf) pre-order, post-order 방식은 이진 트리가 아니여도 사용 가능하다.

그러나 in-order 방식에서는 왼쪽, 오른쪽 자식을 구분하는 기준이 없기 때문에 현재 노드를 언제 방문해야하는지 정해지지 않기 때문에 사용할 수 없다.

 

2. BFS - 트리에서의 최단 경로 탐색에 사용될 수 있다.

트리는 사이클이 존재하지 않는 그래프이다.

사이클이 존재하지 않는 그래프에서는 임의의 두 정점 사이에는 경로가 1개만 존재한다.

그렇기 때문에 트리에서의 두 정점 사이의 경로는 1개뿐이므로 해당 경로가 곧 최단 경로이며

BFS 탐색을 통해 이를 구할 수 있다.

 

 

# 트리의 지름

트리에 존재하는 모든 경로 중 가장 긴 경로를 트리의 지름이라고 한다.

구하는 방법 2가지 

1. 탐색 2번으로 구하기

탐색 1 : 임의의 정점 s에서 모든 정점까지의 거리를 구하고 최장 거리에 위치하는 정점을 u로 둔다.

탐색 2 : 탐색 1로 구한 정점 u에서 모든 정점 까지의 거리를 구하고 최장 거리에 위치하는 정점을 v로 둔다.

이 때, 정점 u와 v 사이의 거리가 트리의 지름이 된다.

2. post-order 이용하기

루트 노드를 v라고 할때, 트리의 지름을 v를 통과하는 경우, 통과하지 않는 경우로 총 2가지가 존재한다.

v를 통과하는 경우 : 트리의 지름은 각각의 자식에서 단말 노드까지의 거리 중 가장 긴 경로 2개를 이용하여 만들 수 있다.

v를 통과하지 않는 경우 : 각각의 자식을 루트로 하는 서브트리에서 다시 트리의 지름을 구하는 것으로 지름을 구한다.

# 그래프의 탐색의 목적 

임의의 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문하는 것

(1번 이상 방문하면 그것은 DFS, BFS가 아님)

 

DFS, BFS는 어떤 순서로 정점을 방문하는 것인가에 차이를 갖는다.

 

# DFS (깊이 우선 탐색)

한 정점에서 시작하여 최대한 깊게 탐색(새로운 연결된 정점이 없을 때까지)하고

더 이상 깊게 탐색할 정점이 없으면 탐색해온 경로를 되돌아오면서 다시 탐색한다.

(새로운 정점 : 방문한 적이 없는 정점)

(사람 1명이 탐색을 하는 것이라고 비유할 수 있다.)

 

 

# BFS (너비 우선 탐색)

탐색을 시작한 정점부터 각 정점에서 방문 가능한(연결되어 있는) 모든 새로운 정점들을 1번에 확인하는 방식으로 탐색한다.

(사람이 연결된 정점의 수만큼 복제되면서 탐색하는 것이라고 비유할 수 있다.)

 

# DFS 구현

- Stack 사용 

더 이상 갈 수 있는 정점이 없을 때, 어디로 돌아가야 하는지 알려주는 역할을 한다.

탐색을 수행해오는 경로를 저장하는 기능을 Stack을 통해 구현한다고 할 수 있다.

cf) Stack이 비면, 모든 정점을 방문하고 탐색을 종료하는 시점이 된다.

- 배열 사용

각 정점에 대한 방문 여부를 저장하는 배열로 사용한다.

 

Stack의 자료 구조와 같은 구조로 작동하는 재귀함수의 특징을 이용하여

DFS는 재귀함수로 구현할 수 있다.

 

아래는 인접 행렬로 표현된 그래프에 대한 DFS를 재귀함수로 구현한 코드이다.

void dfs(int x) {
	check[x] = true; // 방문한 정점은 방문했다고 처리
	for (int i=1; i<=n; i++) { // 각 정점마다 모든 정점에 대해서 확인
		if (a[x][i] == 1 && check[i] == false) { // 두 정점 사이의 간선이 있고, 방문한 적 없는 정점이면
			dfs(i); // 탐색 수행
		}
	}
}

아래는 인접 리스트로 표현된 그래프에 대한 DFS 코드이다.

void dfs(int x) {
	check[x] = true;
	for(int i=0;i<a[x].size();i++) { // 각 정점마다 연결되어 있는 차수만큼 검사
		int y = a[x][i];
		if (check[y] == false) { // 방문한 적 없는 정점이라면
			dfs(y);
		}
	}
}

인접 행렬에 대한 DFS의 시간복잡도는 O(V^2)이고

(모든 정점들을 방문(O(V))하며, 각 방문하는 정점마다 모든 정점에 대한 조건 판별을 수행(*O(V))하기 때문)

인접 리스트에 대한 DFS의 시간복잡도는 O(V+E)이다

(모든 정점들을 방문하며(O(V)), 각 정점들의 차수만큼 조건 판별을 수행하는데, 각 정점들의 차수의 합은 곧 그래프의 간선의 개수와 같기 때문에 O(E)만큼의 시간이 추가로 걸린다고 할 수 있다.

이 때, 항상 V<=E가 성립하기 때문에 인접 리스트에 대한 DFS의 시간복잡도는 O(E)라고 할 수도 있다.

 

# BFS 구현

- Queue 사용

내가 방문해야할 정점들을 Queue를 사용해서 관리한다.

1. 특정 정점에서 방문할 수 있는 모든 정점들을 Queue에 넣는다.

   Queue에 들어가는 정점들은 방문한 것으로 처리되며, Queue에 들어가는 순간 처리된다.

   (Queue에서 나갈떄 처리되면 정점을 중복 방문할 가능성이 생기기 때문)

2. 방문하고 나간 정점은 Queue에서 pop() 해준다. 

3. Queue가 비면, 모든 정점들을 탐색하고 종료되는 시점이 된다.

- 배열 사용 

DFS와 같이 정점의 방문 여부를 기록하기 위한 배열이 필요하다.

 

BFS 알고리즘은 모든 간선들의 가중치가 1일때, 정점 간의 최단 거리를 구할 수 있다는 점에서 중요하다.

 

사실상 알고리즘이 수행하는 기능은 DFS와 같기 때문에 시간복잡도는 DFS와 동일하다.

(인접 행렬 : O(V^2), 인접 리스트 : O(E))

 

아래 코드는 인접 행렬로 구현된 그래프 대해 BFS를 구현한 코드이다.

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
	int x = q.front(); q.pop();
	for (int i=1; i<=n; i++) {
		if (a[x][i] == 1 && check[i] == false) {
			check[i] = true;
			q.push(i);
		}
	}
}

 

아래 코드는 인접 리스트로 구현된 그래프에 대해 BFS를 구현한 코드이다.

queue<int> q;
check[1] = true; 
q.push(1);
while (!q.empty()) {
	int x = q.front(); q.pop();
	for (int i=0;i<a[x].size();i++) {
		int y = a[x][i];
		if (check[y] == false) {
			check[y] = true; q.push(y);
		}
	}
}

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<Edge>(); // 간접 리스트 구현
        for (int i=0;i<n;i++) { // 인접 리스트는 각 정점마다 연결된 간선을 저장하므로
            g[i] = new ArrayList<>(); // 각 정점에 대해 리스트를 할당
        }
        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);
        }
        // 관계는 양방향이므로 입력된 관계*2를 해주어야 간선들의 총 개수가 된다.
        m *= 2;
        // 아래는 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;
                // B-C 친구 관계 여부를 간선 리스트로 확인
                // 서로 다른 두 간선이 연결되어 있는지 확인
                // A-B, C-D가 친구일 때 B-C가 친구인지 확인하는 것
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    // A==B이면 edges i는 간선이 아님
                    // A==C 또는 A==D는 간선 i와 j가 정점 1개를 공유하는 간선이라는 것이다.
                    // (서로 다른 정점 4개를 연결하는 간선이 아닌 것임)
                    continue; // 위 조건에 해당하면 A-B, C-D가 친구일 때 B-C가 친구인지 확인할 수 없으므로 continue (정점 4개에 대한 관계가 아니게 되기 때문)
                }
                // 인접 행렬 사용
                if (!a[B][C]) continue; // A-B, C-D 에서 B-C 관계도 성립하지 않는다면 continue
                // 인접 리스트 사용
                for (int E : g[D]) { // D 정점과 연결된 정점들이 E로 들어온다.
                    if (A == E || B == E || C == E || D == E) continue;
                    // 연결된 정점이 A, B, C, D와 같다면 이는 중복되는 간선이 들어온 것이므로 continue
                    // (D-E 관계에 해당하지 않는다는 것)
                    // 위 조건들을 모두 통과하면 A-B-C-D-E 관계가 존재한다는 것이다.
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        // 위 모든 쌍의 간선들을 확인했음에도 불구하고 모두 조건문에 걸려 continue 처리되어
        // 해당 코드에 다다르면 A-B-C-D-E 관계가 성립하지 않는다는 것이다.
        System.out.println(0);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/13023

그래프 문제는 문제에 나와 있는 상황을 그래프로 모델링해서 푼다.

어떻게 문제의 상황을 그래프로 만드는지가 관건!

 

# 그래프는 G = (V, E)로 나타낸다.

V는 vertex(정점) E는 Edge(간선)의 약자

 

# 사이클 : 정점 A에서 다시 정점 A로 돌아오는 경오

 

# 단순 경로, 단순 사이클 (Simple Path, Simple Cycle)

- 경로, 사이클에서 같은 정점을 2번 이상 방문하지 않는 경로, 사이클이다

- 일반적으로 경로, 사이클로 적혀있을 경우, 이를 의미한다.

 

# 방향 있는 그래프, 방향 없는 그래프 (Directed/Undirected Graph)

- 간선들에 방향이 있으면 directed, 없으면 undirected이다.

 

# 가중치(Weight)

- 간선의 값이다.

- 주로 간선에 해당하는 거리, 시간, 비용을 나타내는데 사용된다.

- 별도로 설정되어 있지않으면 기본적으로 모든 간선의 가중치는 1이다.

 

# 차수(Degree)

- 정점과 연결되어 있는 간선정의 개수

- directed 그래프에서는 이를 in-degree, out-degree로 정점에 들어오는 간선인지, 정점에서 나가는 간선인지 구분하기도 한다.

 

# 그래프를 어떻게 저장하는가? -> 정점과 간선을 저장해야한다.

- 정점 : 정점의 개수를 통해 저장한다. 

   정점이 총 6개라면 각 정점 이름을 0, 1, 2, 3, 4, 5로 설정해서 저장

- 간선 : 정점과 같이 개수로 저장되면 만들 수 있는 그래프의 경우의 수가 다수 존재한다 -> 해당 방법 부적합

 

위와 같은 간선의 특징 때문에 간선을 저장하는 방법이 포인트가 된다.

그리고 한 정점 x와 연결된 간선을 효율적으로 찾는 구조로 그래프를 저장하는 것이 중요하다.

 

# 그래프 저장 방법

 1. 인접 행렬

 2. 인접 리스트

 

# 인접 행렬

정점의 개수를 V라고 했을 때 

V*V 크기의 2차원 배열을 사용하여 그래프를 저장한다.

간선이 있으면, A[i][j] = 1 (가충치가 있다면 가충치의 값)

간선이 없으면, A[i][j] = 0으로 값을 할당한다.

(i, j는 간선 1개를 잇는 2개의 정점을 나타낸다.)

 

인접 행렬을 사용하면 그래프를 저장하는데 V^2 만큼의 공간이 요구된다.

한 정점에 연결된 모든 정점을 구하는 시간복잡도는 O(V)이다.

 

# 인접 리스트

리스트를 이용해서 그래프를 저장한다.

A[i] = j 꼴로 각 정점에 연결되어 있는 정점들을 저장하는 방식으로 간선을 저장한다.

(i, j는 각 정점들을 의미한다.)

리스트 자료구조를 사용하는 이유는 각 정점에 몇 개의 정점이 연결되어 있는지 알 수 없기 때문에

개수 제한 없이 원소 추가가 가능한 리스트를 사용하는 것이다.)

 

일반적으로 LinkedList을 이용해서 구현하며

C++은 vector, JAVA는 Arraylist, Python은 List[] 자료구조를 사용해서 구현한다.

 

# 공간 복잡도

인접 행렬 : O(V^2)

인접 리스트 : O(E)

(V는 정점의 개수, E는 간선의 개수)

 - 인접 행렬은 존재하지 않는 간선에 대한 메모리도 할당되지만, 

   인접 리스트는 존재하는 간선에 대해서만 메모리가 할당되기 때문이다.

(인접 리스트의 경우, 한 정점에 연결된 모든 간선을 찾는 시간복잡도는 O(차수)이다.

 

인접 리스트가 인접 행렬보다 시간적, 공간적으로 효율적이기 때문에

인접 리스트가 더 빈번하게 사용된다.

cf) 임의의 두 정점 사이에 간선이 존재하는지 구하는 경우에만 인접 행렬이 더 유리하다.

    인접 행렬은 각 정점을 잇는 간선을 저장하는 메모리에 접근하여 값이 0이 아닌지 확인하면 되지만(O(1))

    인접 리스트는 해당 정점에 연결된 모든 정점들을 확인해야(O(E)) 이를 판별할 수 있기 때문이다. 

 

다음 코드는 백준 13023번 문제를 해결하기 위해

인접 행렬, 인접 리스트, 간선 리스트를 사용한 코드이다.

 

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<Edge>(); // 간접 리스트 구현
        for (int i=0;i<n;i++) { // 인접 리스트는 각 정점마다 연결된 간선을 저장하므로
            g[i] = new ArrayList<>(); // 각 정점에 대해 리스트를 할당
        }
        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);
        }
        // 관계는 양방향이므로 입력된 관계*2를 해주어야 간선들의 총 개수가 된다.
        m *= 2;
        // 아래는 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;
                // B-C 친구 관계 여부를 간선 리스트로 확인
                // 서로 다른 두 간선이 연결되어 있는지 확인
                // A-B, C-D가 친구일 때 B-C가 친구인지 확인하는 것
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    // A==B이면 edges i는 간선이 아님
                    // A==C 또는 A==D는 간선 i와 j가 정점 1개를 공유하는 간선이라는 것이다.
                    // (서로 다른 정점 4개를 연결하는 간선이 아닌 것임)
                    continue; // 위 조건에 해당하면 A-B, C-D가 친구일 때 B-C가 친구인지 확인할 수 없으므로 continue (정점 4개에 대한 관계가 아니게 되기 때문)
                }
                // 인접 행렬 사용
                if (!a[B][C]) continue; // A-B, C-D 에서 B-C 관계도 성립하지 않는다면 continue
                // 인접 리스트 사용
                for (int E : g[D]) { // D 정점과 연결된 정점들이 E로 들어온다.
                    if (A == E || B == E || C == E || D == E) continue;
                    // 연결된 정점이 A, B, C, D와 같다면 이는 중복되는 간선이 들어온 것이므로 continue
                    // (D-E 관계에 해당하지 않는다는 것)
                    // 위 조건들을 모두 통과하면 A-B-C-D-E 관계가 존재한다는 것이다.
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        // 위 모든 쌍의 간선들을 확인했음에도 불구하고 모두 조건문에 걸려 continue 처리되어
        // 해당 코드에 다다르면 A-B-C-D-E 관계가 성립하지 않는다는 것이다.
        System.out.println(0);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/13023

0. PostMan을 설치하고 New를 통해 새로운 공간을 할당한다. 

 

1. 사용하고자하는 API의 json 출력을 Postman을 통해 받는다.

GET으로 받아오는 json 데이터의 출력 결과를 밑의 창으로 확인할 수 있다.

(해당 예시는 네이버 영화 검색 API의 출력 결과를 가져온다.)

(네이버 api의 경우 Header 데이터로 네이버 api 사용 등록 시에 제공되는 clientId와 clientSecret을 보내야 접근 권한이 주어진다.)

 

2. http://www.jsonschema2pojo.org/로 이동하여 PostMan을 통해 얻은 json 출력결과를 붙여넣고 조건에 맞게 체크박스를 설정하고 하단의 Zip 버튼을 누른다.

 

(위 설정은 retrofit을 사용하고 gson converter를 사용하는 자바 기반의 안드로이드를 위한 모델을 제공하는 파일을 만들도록 설정하였다.)

 

3. Zip 파일을 누르면 자동으로 생성되는 모델.java 파일을 얻을 수 있다.

(위 예시의 경우에는 Movie.java와 Item.java 2개의 파일이 자동으로 생성된다.)