데일리썽

문제 제목 : 효율적인 해킹

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main8 {
    public static int pcCnt, connCnt, hackingCnt, maxHackingCnt;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[10001];

    public static Integer bfs(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(node);
        visited = new boolean[10001];
        visited[node] = true;

        hackingCnt = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int adjNode : adjList.get(now)) {
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;
                    hackingCnt++;
                }
            }
        }

        return hackingCnt;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        pcCnt = Integer.parseInt(st.nextToken());
        connCnt = Integer.parseInt(st.nextToken());

        for (int i = 0; i < pcCnt + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < connCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int pc1 = Integer.parseInt(st.nextToken());
            int pc2 = Integer.parseInt(st.nextToken());
            adjList.get(pc2).add(pc1);
        }

        maxHackingCnt = 0;
        List<Integer> resultList = new ArrayList<Integer>();
        for (int i = 1; i < pcCnt + 1; i++) {
            int cnt = bfs(i);

            if (cnt > maxHackingCnt) {
                maxHackingCnt = cnt;
                resultList = new ArrayList<>();
                resultList.add(i);
            } else if (cnt == maxHackingCnt) {
                resultList.add(i);
            }
        }

        for (Integer result : resultList) {
            System.out.print(result + " ");
        }
    }
}

문제 제목 : 유기농 배추

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static int t, m, n, k;
    public static int[][] ground = new int[50][50];
    public static boolean[][] visited = new boolean[50][50];

    public static int[] moveX = {0, 0, -1, 1};
    public static int[] moveY = {1, -1, 0, 0};

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + moveX[i];
                int nextY = nowY + moveY[i];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if (ground[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                        queue.offer(new int[] {nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = x + moveX[i];
            int nextY = y + moveY[i];

            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                if (ground[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                    dfs(nextX, nextY);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            m = sc.nextInt();
            n = sc.nextInt();
            k = sc.nextInt();

            ground = new int[50][50];
            visited = new boolean[50][50];

            for (int j = 0; j < k; j++) {
                int y = sc.nextInt();
                int x = sc.nextInt();
                ground[x][y] = 1;
            }

            int result = 0;

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (ground[j][k] == 1 && !visited[j][k]) {
                      //  bfs(j, k);
                        dfs(j, k);
                        result++;
                    }
                }
            }

            System.out.println(result);
        }
    }
}

문제 제목 : 바이러스

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static int pcCnt;
    public static int connCnt;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[101];
    public static int resulCnt;

    public static void addEdge(int n, int m) {
        adjList.get(n).add(m);
    }

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

        while (!queue.isEmpty()) {
            int now = queue.poll();
            resulCnt++;
            for (int i = 0; i < adjList.get(now).size(); i++) {
                int adjNode = adjList.get(now).get(i);
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;

                }
            }
        }


    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        pcCnt = sc.nextInt();
        connCnt = sc.nextInt();

        for (int i = 0; i < pcCnt + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < connCnt; i++) {
            int pc1 = sc.nextInt();
            int pc2 = sc.nextInt();
            addEdge(pc1, pc2);
            addEdge(pc2, pc1);
        }

        bfs(1);
        System.out.println(resulCnt - 1);
    }
}

문제 제목 : 숨바꼭질

난이도 : 하

문제 유형 : BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.*;

public class Main {
    public static int n, k;
    public static int MAX = 100001;
    public static boolean[] visited = new boolean[MAX];
    public static int[] time = new int[MAX];

    public static Integer bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        visited[n] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if (now == k) return time[now];

            int next = now - 1;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }

            next = now + 1;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }

            next = now * 2;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        System.out.println(bfs());
    }
}

문제 제목 : DFS와 BFS

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.*;

public class Main {
    public static Integer n, m, v;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[1001];

    public static void addEdge(int n, int m) {
        adjList.get(n).add(m);
    }

    public static void dfs(int node) {
        if (visited[node]) return;

        visited[node] = true;
        System.out.print(node + " ");

        for (int i = 0; i < adjList.get(node).size(); i++) {
            dfs(adjList.get(node).get(i));
        }
    }

    public static void bfs(int node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(node);
        visited[node] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");
            for (int i = 0; i < adjList.get(now).size(); i++) {
                int adjNode = adjList.get(now).get(i);
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();

        for (int i = 0; i < n + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            addEdge(x, y);
            addEdge(y, x);
        }

        for (int i = 1; i < n + 1; i++) {
            Collections.sort(adjList.get(i));
        }

        dfs(v);
        System.out.println();
        visited = new boolean[1001];
        bfs(v);
    }
}

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

2. BFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void bfs (Integer newNode) {
        Boolean visited[] = new Boolean[node];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[newNode] = true;
        queue.add(newNode);

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.println(now + " ");
            for (int i = 0; i < adj.get(now).size(); i++) {
                int adjNode = adj.get(now).get(i);
                if (!visited[adjNode]) {
                    visited[adjNode] = true;
                    queue.add(adjNode);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

3. 시간 복잡도

노드수 : V

간선수 : E

시간 복잡도 : O(V + E)