2024/03/04(월)

Part. 알고리즘

백준 - 1325번 효율적인 해킹

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

문제를 풀지 못하였다..

그래프만 나오면 겁을 먹는것 같다. 겁먹지말고 도전해보자!

 

책에서 알려주는 문제 분석하기

신뢰관계가 A,B라고 할때, A가 B를 신뢰한다는 것이다. 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢸를 가장 많이 받는 컴퓨터이다.

그래프의 노드와 에지를 기준으로 이해하면 A라는 노드에서 탐색 알고리즘으로 방문하는 노드가 B,C라고 하면 B,C는 A에게 신뢰받는 노드가 됩니다.

 

책에서 알려주는 손으로  풀어보기

(1) 인접 리스트로 컴퓨터와 신뢰 관계 데이터의 그래프를 표현한다.

(2) 모든 노드로 각각 BFS 탐색 알고리즘을 적용해 탐색을 수행한다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 준다.

(3) 탐색 종료 후 신뢰도 배열을 탐색해 신뢰도의 최댓값을 Max값으로 지정하고, 신뢰도 배열을 다시 탐색하면서 Max값을 지니고 있는 노드를 오름차순 출력한다.

 

1차 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static int N, M;
    public static boolean[] visited;
    public static int[] answer;
    public static ArrayList<Integer>[] A;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new ArrayList[N + 1];
        answer = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            A[S].add(E);
        }

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            bfs(i);
        }

        int maxVal = Integer.MIN_VALUE;

        for (int i = 1; i < answer.length; i++) {
            maxVal = Math.max(maxVal, answer[i]);
        }

        System.out.println(Arrays.toString(answer));

        for (int i = 1; i <= N; i++) {
            if (answer[i] == maxVal) {
                System.out.print(i + " ");
            }
        }

        br.close();
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i : A[cur]) {
                if (visited[i] == false) {
                    visited[i] = true;
                    answer[i]++; // 신규노드 인덱스 배열 증가
                    queue.add(i);
                }
            }
        }
    }
}

 

시간초과가 발생한다.. 명확한 해결 방법을 모르겠다.(일단 킵)

BufferedWriter를 사용해도 시간이 초과된다.

 

백준 - 1707번 이분 그래프 판별하기

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

이 문제도 접근하다가 풀지 못했다.

애초에 이 문제에서 이분 그래프가 무엇인지?에 대해서도 이해하지 못했다.

 

검색한 정보

 

이분 그래프란?

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프

 

이분 그래프의 특징

(1) 이분 그래프 확인 여부는 BFS, DFS 탐색을 이용하면 된다.

(2) 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 무조건 같은 색으로 칠한다.

(3) 연결 성분의 개수를 구하는 방법과 유사하다.

(4) 모든 정점을 방문하며 간선을 검사하므로 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.

 

이분 그래프인지 확인하는 방법

- 서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.

(1) BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.

(2) 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.

(3) 탐색을 진행시 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.

    - BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다.

(4) 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.

 

주의할 점: 연결 그래프와 비연결 그래프를 둘 다 고려 해야 한다.

그래프가 비연결 그래프인 경우 모든 정점에 대해서 확인하는 작업이 필요하다.

 

참고 자료: https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

 

책에서 알려주는 손으로 풀어보기

(1) 입력된 그래프 데이터를 인접 리스트로 구현한다.

(2) 모든 노드로 DFS 탐색 알고리즘을 적용해 탐색을 수행한다. DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방분한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별

(3) 이분 그래프 여부를 정답으로 출력

(4) testCase만큼 반복

 

1차 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    public static int K;
    public static int V;
    public static int E;
    public static ArrayList<Integer>[] list;
    public static boolean[] visited;
    public static boolean isCheck;
    public static int[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            visited = new boolean[V + 1]; // 1번 노드부터
            check = new int[V + 1];
            list = new ArrayList[V + 1];
            isCheck = true; // 테스트 케이스마다 초기화

            for (int j = 1; j <= V; j++) { // 초기화
                list[j] = new ArrayList<>();
            }

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken());
                int node2 = Integer.parseInt(st.nextToken());

                //
                list[node1].add(node2);
                list[node2].add(node1);
            }

            for (int j = 1; j <= V; j++) {
                if (isCheck) { // 이분그래프가 아닌 경우
                    dfs(j);
                } else {
                    break;
                }
            }

            if (isCheck) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    public static void dfs(int node) {
        visited[node] = true;
        for (int value : list[node]) {
            if (!visited[value]) { // 방문 안한 경우
                check[value] = (check[node] + 1) % 2; // 이전 노드와 다른 집합으로 저장
                dfs(value);
            } else if (check[node] == check[value]) { // 이미 방문하고, 인접 노드가 같은 수인 경우
                isCheck = false; // 이분 그래프가 아니다!
            }
        }
    }
}

 

나에게 하고 싶은 말

이분 그래프에 대한 개념을 이해하자!

 

백준 - 2251번 물통

https://www.acmicpc.net/problem/2251

2251번: 물통

 

어떻게 접근을 해야할지 조차 모르는 문제

자신감이 너무 떨어진다. 코딩 테스트를 이렇게 해서 합격이 가능할까..?

 

책에서 알려준 문제 분석하기

그래프 데이터를 저장하고 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다.

A,B,C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고, 문제에 접근하라

 

책에서 알려준 손으로 풀어 보기

(1) 처음에 물통 A,B는 비어있고 C는 꽉 차 있으므로 최소 출발 노드를 (0,0,3번째 물통의 용량)으로 초기화한다.

[0][0][10]

 

(2) BFS를 수행

탐색 과정

1. 노드에서 갈 수 있는 6개의 경우(A ➡️ B, A ➡️ C, B ➡️ A, B ➡️ C, C ➡️ A, C ➡️ B)에 관해 다음 노드로 정해 큐에 추가한다.

A,B,C가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않는다.

 

2. 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다. 단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남긴다.

 

3. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 배열에 추가한다.