데일리썽

문제 제목 : 효율적인 해킹

난이도 : 하

문제 유형 : 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);
    }
}

문제 제목 : 가장 높은 탑 쌓기

난이도 : 상

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 50분 (못하면 2배 100분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static class Brick {
        public Integer index;
        public Integer area;
        public Integer height;
        public Integer weight;

        public Brick(Integer index, Integer area, Integer height, Integer weight) {
            this.index = index;
            this.area = area;
            this.height = height;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        ArrayList<Brick> brickList = new ArrayList<Brick>();

        brickList.add(new Brick(0, 0, 0, 0));
        for (int i = 1; i < n + 1; i++) {
            brickList.add(new Brick(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(brickList, (s1, s2) -> s1.weight - s2.weight);

        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (brickList.get(i).area > brickList.get(j).area) {
                    dp[i] = Math.max(dp[i], dp[j] + brickList.get(i).height);
                }
            }

        }

        Integer maxHeight = Arrays.stream(dp).max().getAsInt();

        int index = n;
        ArrayList<Integer> resultList = new ArrayList<>();
        while (index != 0) {
            if (maxHeight == dp[index]) {
                resultList.add(brickList.get(index).index);
                maxHeight -= brickList.get(index).height;
            }
            index -= 1;
        }

        System.out.println(resultList.size());
        for (int i = resultList.size() - 1; i >= 0; i--) {
            System.out.println(resultList.get(i));
        }
    }
}

문제 제목 : 기타리스트

난이도 : 중

문제 유형 : 동적 프로그래밍(DP

추천 풀이 시간 : 40분 (못하면 2배 80분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        Integer s = sc.nextInt();
        Integer m = sc.nextInt();
        ArrayList<Integer> diffList = new ArrayList<Integer>();
        int[][] dp = new int[51][1001];
        
        for (int i = 0; i < n; i++) {
            diffList.add(sc.nextInt());
        }
        
        dp[0][s] = 1;
        
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < m + 1; j++) {
                if (dp[i - 1][j] == 0) continue;
                if (j - diffList.get(i - 1) >= 0) {
                    dp[i][j - diffList.get(i - 1)] = 1;
                }
                if (j + diffList.get(i - 1) <= m) {
                    dp[i][j + diffList.get(i - 1)] = 1;
                }
            }
        }
        
        int result = -1;
        for (int i = m; i >= 0; i--) {
            if (dp[n][i] == 1) {
                result = i;
                break;
            }
        }
        
        System.out.println(result);
    }
}

문제 제목 : LCS

난이도 : 하

문제 유형 : 동적 프로그래밍(DP), LCS

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

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int[][] dp = new int[1001][1001];
        
        for (int i = 1; i < str1.length() + 1; i++) {
            for (int j = 1; j < str2.length() + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        
        System.out.println(dp[str1.length()][str2.length()]);
    }
}