📙[Algo] 24.09.10 ~ 24.09.16 알고리즘

알고리즘 문제) BOJ 18188.다오의 데이트

• 링크 : https://www.acmicpc.net/problem/18188

문제 요약

• N개의 명령이 주어진다
  • 각 명령은 움직일 수 있는 방향 2개가 주어진다
• 다오가 명령에서 주어진 방향 중 하나를 선택해, 한칸씩 이동할 떄, 디지니를 만날 수 있는지를 찾아라
  • 블록과 경계밖으로는 이동할 수 없다

시간 제한

• 1초

입력

• 맵크기 세로H와 가로W가 주어진다
• H개의 줄에 맵 정보가 주어진다
  • . : 빈칸
  • D : 디오 위치
  • Z : 디지니 위치
  • @ : 블록
• 명령 개수 N개가 주어진다
  • 각 명령마다 이동 가능한 방향 2개가 주어진다
    • W : 위
    • S : 아래
    • A : 왼쪽
    • D : 오른쪽

출력

• 만날 수 없다면 NO
• 만날 수 있다면 YES를 출력하고, 어떻게 움직였는지 방향도 출력해라
  • 여러 방법이 있다면 아무거나 출력해도 된다.

접근법

• DFS
  • 매개변수로 현재위치 cr , cc와 몇번째 명령에 대한 수행인지 나타내는 nth를 매개변수로 갖는 재귀함수 생성
  • 이때, 방문체크는 3차원으로 선언 ⇒ 몇 번째 명령에 방문했는지에 따라 방문 체크를 해야한다.
    • 늦게 재방문했을 때 그 경로로 디지니를 만날 수도 있으니까
  • 방향 정보를 기록하기 위해 log배열에 현재 명령 번호nth인덱스일 때, 방향을 기록했다.
  • 만약 현재 위치가 디지니 위치라면 1을 return했고, 재귀호출 부분의 반환값이 0보다 클 경우 무조건 1을 return 하도록했다. ⇒ 경로를 기록하는 log배열이 갱신되는 것을 방지

코드

import java.io.*;
import java.util.*;

public class Main {
    static int H, W, N;
    static char[][] arr = new char[21][21];
    static char[][] cmd = new char[21][2];
    static int[] delR = {-1, 1, 0, 0}; // 상 하 좌 우
    static int[] delC = {0, 0, -1, 1};
    static char[] dir = {'W', 'S', 'A', 'D'};
    static boolean[][][] visited = new boolean[21][21][21];
    static int[] log = new int[21];
    static int sr, sc, er, ec;

    static int dfs(int cr, int cc, int nth) {
        if (cr == er && cc == ec) {
            N = nth - 1;
            return 1;
        }
        if (nth > N) return 0;

        int mr, mc, dir;
        for (int i = 0; i < 2; i++) {
            dir = cmd[nth][i];
            mr = cr + delR[dir];
            mc = cc + delC[dir];

            if (mr < 1 || mc < 1 || H < mr || W < mc
                    || arr[mr][mc] == '@' || visited[nth][mr][mc]) continue;

            visited[nth][mr][mc] = true;
            log[nth] = dir;
            if (dfs(mr, mc, nth + 1) > 0) return 1;
            visited[nth][mr][mc] = false;
        }

        return 0;
    }

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

        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        String input;
        for (int i = 1; i <= H; i++) {
            input = br.readLine();
            for (int j = 1; j <= W; j++) {
                arr[i][j] = input.charAt(j - 1);
                if (arr[i][j] == 'D') {
                    sr = i;
                    sc = j;
                } else if (arr[i][j] == 'Z') {
                    er = i;
                    ec = j;
                }
            }
        }

        N = Integer.parseInt(br.readLine());
        char c;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                c = st.nextToken().charAt(0);
                if (c == 'W') cmd[i][j] = 0;
                else if (c == 'S') cmd[i][j] = 1;
                else if (c == 'A') cmd[i][j] = 2;
                else if (c == 'D') cmd[i][j] = 3;
            }
        }

        int ret = dfs(sr, sc, 1);

        if (ret == 1) {
            System.out.println("YES");
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= N; i++) {
                sb.append(dir[log[i]]);
            }
            System.out.println(sb);
        } else System.out.println("NO");
    }
}

 

알고리즘 문제) BOJ 3187.양치기 꿍

• 링크 : https://www.acmicpc.net/problem/3187

문제 요약

• 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다
• 그외의 경우는 양이 전부 잡아먹힌다.
• 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산해라

시간 제한

• 1초

입력

• 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)
• 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호를 의미

출력

• 살아남게 되는 양과 늑대의 수를 각각 순서대로 출력

접근법

• 맵을 순회하면서 방문하지 않은 빈칸을 만난 경우 dfs를 돌렸다.
  • dfs를 돌면서 울타리안의 공간을 순회하면서, 양과 늑대의 개수를 카운트했다.
  • 다 돌고 났을 때 양과 늑대의 개수를 비교하여, 양이 더 많을 경우 살아남은 양의 수에 누적해서 더하고, 그 반대의 경우에는 늑대 수에 누적해서 더했다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int R, C;
    static char[][] arr;
    static boolean[][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int wolf, sheep;

    static void dfs(int cr, int cc) {
        visited[cr][cc] = true;
        if (arr[cr][cc] == 'v') wolf++;
        else if (arr[cr][cc] == 'k') sheep++;

        int mr, mc;
        for (int dir = 0; dir < 4; dir++) {
            mr = cr + delR[dir];
            mc = cc + delC[dir];

            if (mr < 0 || mc < 0 || R <= mr || C <= mc
                    || arr[mr][mc] == '#' || visited[mr][mc]) continue;

            dfs(mr, mc);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visited = new boolean[R][C];

        String input;
        for (int i = 0; i < R; i++) {
            input = br.readLine();
            for (int j = 0; j < C; j++) {
                arr[i][j] = input.charAt(j);
            }
        }

        int wfSum = 0, spSum = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (visited[i][j] || arr[i][j] == '#') continue;
                dfs(i, j);

                if (wolf < sheep) {
                    spSum += sheep;
                } else {
                    wfSum += wolf;
                }

                wolf = 0;
                sheep = 0;
            }
        }

        System.out.println(spSum + " " + wfSum);
    }
}

 

알고리즘 문제) BOJ 29195.Yes or yes

• 링크 : https://www.acmicpc.net/problem/25195

문제 요약

• 1번정점에서 더이상 이동할 수 없는 정점으로 이동하는 경로에서 팬을 만나지 않을 수 있은 경로가 있는지 판단 → 있다면 yes, 불가능하다면 Yes
• 그래프는 무사이클, 유방향그래프

시간 제한

• 1초

입력

• 정점 개수 N, 간선 개수 M
  • 1 ≤ N, M ≤ 10만
• M개의 줄에 간선 정보 a, b
  • a → b로 가는 경로 존재
• 팬이 존재하는 정점 개수 S
  • 1 ≤ S ≤ N
• 각 팬이 존재하는 정점 번호를 의미하는 정수 S개가 주어짐

출력

• 있다면 yes, 불가능하다면 Yes

접근법

• dfs로 더이상 이동할 수 없을 때까지 이동
  • → 그 과정에서 팬이 있는 정점을 만난다면 return 1
  • 만약 끝까지 이동했는데 없다면 return 0
• 최종적으로 가장 작은 값을 반환할 수 있도록 ret변수를 최솟값으로 갱신
• 이때, dfs 반환값이 0보다 크다면 Yes, 아니라면 yes 출력

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, S;
    static ArrayList<Integer>[] lst;
    static boolean[] fans = new boolean[100_010];

    static int dfs(int cur) {
        if (fans[cur]) return 1;
        if (lst[cur].isEmpty()) return 0;

        int ret = 1 << 30;
        for (Integer nxt : lst[cur]) {
            ret = Math.min(ret, dfs(nxt));
        }
        return ret;
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

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

            lst[a].add(b);
        }

        S = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < S; i++) {
            fans[Integer.parseInt(st.nextToken())] = true;
        }

        int ret = dfs(1);

        if (ret > 0) System.out.println("Yes");
        else System.out.println("yes");
    }
}

 

알고리즘 문제) BOJ 22513. 빠른 오름차순 숫자 탐색

• 링크 : https://www.acmicpc.net/problem/25513

문제 요약

• 보드의 격자에는 -1, 0, 1, 2, 3, 4, 5, 6중 하나의 수가 적혀 있다
• 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가한다
  • 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다
• -1이 적혀 있는 칸으로는 이동할 수 없고 0, 1, 2, 3, 4, 5, 6이 적혀 있는 칸으로는 이동할 수 있다
• 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서대로 방문하려고 한다.
• i가 적혀 있는 칸에서 i + 1이 적혀 있는 칸으로 이동할 때 다른 번호가 적힌 칸을 방문해도 된다.(1 ≤ i ≤ 5) 마찬가지로, 현재 위치 (r, c)에서 1이 적혀 있는 칸으로 이동할 때 다른 번호가 적힌 칸을 방문해도 된다.
• 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서대로 방문하는 최소 이동 횟수를 출력하자.

시간 제한

• 1초

입력

• i번째 줄의 j번째 수는 보드의 (i - 1)번째 행, (j - 1)번째 열에 적혀있는 수를 나타낸다
• 보드의 각 칸에 적혀 있는 수는 -1, 0, 1, 2, 3, 4, 5, 6중 하나이다.
  • 1, 2, 3, 4, 5, 6이 적혀 있는 칸이 1개씩 주어진다.
• 다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.
  • 0 ≤ r, c ≤ 4
  • 학생의 현재 위치 (r, c)에는 0이 적혀 있다.

출력

• 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서대로 방문하는 최소 이동 횟수를 출력
  • 방문할 수 없는 경우 -1을 출력

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr = new int[5][5];
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int sr, sc;

    static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] visited = new boolean[5][5][10];
        q.offer(new int[]{sr, sc, 0});
        visited[sr][sc][0] = true;

        int cr, cc, mr, mc, prv, size, ans = 0;
        while (!q.isEmpty()) {
            size = q.size();
            for (int s = 0; s < size; s++) {
                cr = q.peek()[0];
                cc = q.peek()[1];
                prv = q.poll()[2];

                if (prv == 6) return ans;

                for (int dir = 0; dir < 4; dir++) {
                    mr = cr + delR[dir];
                    mc = cc + delC[dir];

                    if (mr < 0 || mc < 0 || 5 <= mr || 5 <= mc
                            || arr[mr][mc] == -1 || visited[mr][mc][prv]) continue;

                    if (arr[mr][mc] == prv + 1) {
                        visited[mr][mc][prv + 1] = true;
                        q.offer(new int[]{mr, mc, prv + 1});
                    } else {
                        visited[mr][mc][prv] = true;
                        q.offer(new int[]{mr, mc, prv});
                    }
                }
            }
            ans++;
        }
        return -1;
    }

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

        for (int i = 0; i < 5; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        sr = Integer.parseInt(st.nextToken());
        sc = Integer.parseInt(st.nextToken());

        int ret = bfs();
        System.out.println(ret);
    }
}

 

알고리즘 문제) BOJ 2829. 아름다운 행렬

• 링크 : https://www.acmicpc.net/problem/2829

문제 요약

• A를 행렬의 주 대각선 성분의 합, B는 또다른 대각선 성분의 합
  • 이때, 행렬의 아름다운 정도는 A-B
• N×N크기의 행렬이 주어졌을 때, 아름다운 정도가 가장 큰 부분 행렬을 구하는 프로그램을 작성
• 주 대각선은 행렬의 가장 왼쪽 위에서 시작하는 대각선

시간 제한

• 1초

입력

• 첫째 줄에 행렬의 크기 N이 주어진다. (2 ≤ N ≤ 400)
• 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다.

출력

• 주어진 행렬의 부분 행렬 중 아름다운 정도가 가장 큰 것의 아름다운 정도를 출력

접근법

• a대각선, b대각선의 누적합 배열을 모두 구해준다
• 이후, size가 1~N일때의 부분 행렬들을 모두 탐색하면서 합계의 차이가 가장 큰 값을 찾았다. ⇒ N이 400이므로 N^3이 가능

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] aPrefix;
    static int[][] bPrefix;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine().trim());
        aPrefix = new int[N + 2][N + 2];
        bPrefix = new int[N + 2][N + 2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j <= N; j++) {
                aPrefix[i][j] = Integer.parseInt(st.nextToken());
                bPrefix[i][j] = aPrefix[i][j];
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                aPrefix[i][j] = aPrefix[i - 1][j - 1] + aPrefix[i][j];
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                bPrefix[i][j] = bPrefix[i - 1][j + 1] + bPrefix[i][j];
            }
        }

        int max = Integer.MIN_VALUE, sumA, sumB;
        for (int size = 1; size <= N; size++) {
            for (int row = size; row <= N; row++) {
                for (int col = size; col <= N; col++) {
                    // size 2, row 3, col 3
                    sumA = aPrefix[row][col] - aPrefix[row - size][col - size];
                    sumB = bPrefix[row][col - size + 1] - bPrefix[row - size][col + 1];
                    max = Math.max(max, sumA - sumB);
                }
            }
        }

        System.out.println(max);
    }
}

 

알고리즘 문제) BOJ 20917.사회적 거리 두기

• 링크 : https://www.acmicpc.net/problem/20917

문제 요약

• 각 테스트케이스 별로 n개의 좌석중 s개의 좌석을 선택했을 때, 가장 가까운 거리가 최대가 되는 경우를 찾아라

시간 제한

• 1초

입력

• 테스트케이스의 수 T
  • 1 ≤ T ≤ 10
• n s
  • 2 ≤ s ≤ n ≤ 20만
• 좌석 후보 위치 x[i]가 n개
  • 1 ≤ x[i] ≤ 10억

출력

• 테케별로 가장 가까운 좌석의 거리가 최대가 되는 경우를 찾아라

접근법

• 매개변수탐색 ⇒ 최소가 최대가되는 경우 찾기
  • 가장 가까운 거리를 mid값으로 가정한 뒤, 좌석을 순회하면서 두 좌석 거리가 mid보다 크거나 같은경우 카운트
  • 카운트한 값이 s보다 크거나 같다면 정답이 될 수 있는 후보로 판단하여 정답변수 갱신 후, 더 큰 값을 찾도록 start를 mid+1로 갱신
  • 만약 s보다 작다면, mid값을 너무 크게 가정한 것이므로 end를 mid-1로 갱신

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, s;
    static int[] x;

    // 11 17 19 21 22 23 28
    static int parametricSearch() {
        int start = 0, end = x[n - 1] - x[0], mid, cnt, pre, ans = -1;
        while (start <= end) {
            mid = (start + end) / 2;
            cnt = 0;
            pre = 0;
            for (int i = 1; i < n; i++) {
                if (x[i] - x[pre] >= mid){
                    cnt++;
                    pre = i;
                }
            }
            cnt++;

            if (cnt >= s) {
                ans = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            x = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                x[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(x);
            int ret = parametricSearch();
            sb.append(ret).append("\\n");
        }
        System.out.println(sb);
    }
}