📙[Algo] 24.09.06 ~ 24.09.08 알고리즘

알고리즘 문제) BOJ 14923. 미로탈출

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

문제 요약

• N*M 미로가 존재
• 출발위치는 (Hx,Hy)이며, 미로 탈출 위치는 (Ex, Ey)이다
• 미로에는 벽이 존재하며, 통과가 불가능하다
• 그러나, 한번 마법을 부리면 벽을 허물 수 있다
• 미로를 탈출 할 수 있는지 알아보고, 가능하다면 최단 경로 D를 출력해라

시간 제한

• 1초

입력

• 미로 크기 N * M
  • 2 ≤ N ≤ 1000
  • 2 ≤ M ≤ 1000
• 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
  • 출발위치랑 탈출위치는 다름
• 행렬 정보가 주어짐다
  • 0 : 빈공간
  • 1 : 벽

출력

• 최단 경로 D 출력해라
  • 탈출 할 수 없다면 -1출력

접근법

• 최단 경로 알고리즘 BFS를 사용해 접근
• BFS를 돌리며 방문체크 할 때, 현재 마법을 썼는냐, 안 썼느냐에 따라 2가지 상태가 존재할 수 있으므로, 방문체크 visited 배열을 3차원으로 선언했다.
  • visited[row][col][0] : 아직 마법을 쓰지 않고 row, col에 위치
  • visited[row][col][1] : 마법을 쓰고 row, col에 위치
• 큐에는 현재위치와 마법 사용 여부를 담은 크기 3짜리 배열을 담았다 {row, col, use}
  • 벽을 만나지 않았다면, 해당 위치를 큐에 담고 방문 체크했고,
  • 만약 벽을 만났을 때
    • 마법을 썼다면(use > 0) 그냥 pass하고
    • 마법을 쓰지 않았다면 마법을 부리고 벽을 부순 뒤 해당 위치를 큐에 담고 방문 체크했다.

코드

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

public class Main {
    static int N, M, hx, hy, ex, ey;
    static int[][] arr;
    static boolean[][][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{hx, hy, 0});
        visited[hx][hy][0] = true;

        int cr, cc, use, mr, mc, size, dist = 0;
        while (!q.isEmpty()) {
            size = q.size();

            for (int s = 0; s < size; s++) {
                cr = q.peek()[0];
                cc = q.peek()[1];
                use = q.poll()[2];

                if (cr == ex && cc == ey) {
                    return dist;
                }

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

                    if (mr < 0 || mc < 0 || N <= mr || M <= mc || visited[mr][mc][use]) continue;

                    // 벽을 만났다면
                    if (arr[mr][mc] > 0) {
                        // 이미 써버려서 마법 못 쓸 경우 pass
                        if (use > 0) continue;
                        // 마법쓰기
                        visited[mr][mc][arr[mr][mc]] = true;
                        q.offer(new int[]{mr, mc, arr[mr][mc]});
                    } else {
                    //벽이 아니라면
                        visited[mr][mc][use] = true;
                        q.offer(new int[]{mr, mc, use});
                    }
                }
            }
            dist++;
        }

        return -1;
    }

    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());
        st = new StringTokenizer(br.readLine());
        hx = Integer.parseInt(st.nextToken()) - 1;
        hy = Integer.parseInt(st.nextToken()) - 1;
        st = new StringTokenizer(br.readLine());
        ex = Integer.parseInt(st.nextToken()) - 1;
        ey = Integer.parseInt(st.nextToken()) - 1;

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

        // 여기서 굳이 몇번 벽을 부쉈는지 체크할 필요 X-> 그냥 마법을 부렸는지만 체크하면 된다
        visited = new boolean[N][M][2];

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

    }
}

 

알고리즘 문제) BOJ 2166. 타일 위의 대각선

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

문제 요약

• 한 변의 길이가 1cm인 정사각형 타일 존대
• 이 타일들이 가로가 xcm 세로가 ycm인 직사각형 모양 벽에 빈틈없이 붙어있음
• 이 직사각형에 하나의 대각선을 그렸을 때, 타일들 중 대각선이 그려져 있는 타일 개수를 구하자!!!

시간 제한

• 1초

입력

• 가로 길이 xcm, 세로 길이 ycm
  • x,y는 10억 이하 자연수
  • x와 y사이에는 빈칸이 하나 이상 존재

출력

• 대각선이 그려져 있는 타일 개수 구하기

접근법

• 유클리드 호제법으로 구하는 문제였다.
• 직사각형 모양의 벽을 좌표로 대입했을 때,
  • (0,y) 와 (x,0)을 지나는 대각선을 가진 직사각형을 볼 수 있다.
• 이때, 직사각형에 대각선을 그으면, 정수 좌표를 기준으로 작은 사각형 여러 개를 나눌 수 있는데, 그 개수는 x와 y의 최대공약수가 된다.
  • 예를들어, x=8, y=12일때, 최대공약수는 4가되는데, 이는 2 * 3크기의 작은 사각형 4개로 나눌 수 있으며, 각각 작은 사각형은 동일한 패턴으로 타일을 지나게 된다.
• 따라서, GCD(x,y)로 작은 사각형의 수 boxCnt를 구한 뒤에, 작은 사각형 변의 길이로 x, y를 갱신해준다.
• 그다음 작은 사각형에서 대각선이 지나는 타일의 개수를 구해야하는데,
  • 다음과같은 규칙성을 발견할 수 있다.
    • 대각선이 지나는 가로선 개수는 y - 1개이며, 세로선 개 수는 x - 1개가 된다.
    • 또한 처음 지나는 타일의 수를 고려해 마지막에 + 1을 해준다.
• 최종적으로 대각선이 지나는 타일 개수는 boxCnt * (x + y - 1)이 된다.

코드

• 원래코드

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

public class Main {

    static int getGCD(int a, int b) {
        int temp = 0;
        while (a % b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }

        return b;
    }

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

        // 대각선을 이을 때, 정점과 정점을 잇는 가장 작은 사각형 개수 찾기
        int boxCnt = getGCD(x, y);
        // 작은 사각형의 끝 정점(대각선을 이을 때 최초로 만나는 정점)
        int mx = x / boxCnt;
        int my = y - (y / boxCnt);
        // 직선그래프 기울기
        double a = - ((double)y / x);
        // 직선 그래프 y절편
        int b = y;

        // 작은 사각형에서 대각선이 지나는 사각형 개수 구하기
        int sum = 0; double ty, py = y - 1;
        for (int tx = 1; tx <= mx; tx++) {
            ty = a * tx + b;
            sum += (int) py - (int) ty + 1;
            py = ty;
        }

        System.out.println(sum * boxCnt);

    }
}

• 개선된 코드

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

public class Main {

    static int getGCD(int a, int b) {
        int temp = 0;
        while (a % b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }

        return b;
    }

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

        // 대각선을 이을 때, 정점과 정점을 잇는 가장 작은 사각형 개수 찾기
        int boxCnt = getGCD(x, y);

        // 작은 사각형에서 대각선이 지나는 타일 개수 구하기
        // 작은사각형의 크기 x, y로 갱신
        y /= boxCnt;
        x /= boxCnt;
        // 대각선을 그었을 때
        // 가로선은 y-1개만큼, 세로선은 x-1개만큼 지난다
        // 따라서 대각선이 지나는 타일 개수는 x-1 + y-1 + 1이 된다.
        System.out.println(boxCnt * (x + y - 1));

    }
}

 

알고리즘 문제) BOJ 12355. Ocean View (Large)

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

문제 요약

• 1번집부터 N번집까지 번호가 매겨져 있음(서쪽 - 동쪽)
  • 이때 호수는 호수 서쪽에 있다.
• 또한, 집들은 각 높이가 다르다
• 이때, 각 주민들은 호수의 경치를 보고 싶은 데, 더 높이가 높은 집이 시야를 가릴 수 있다.
  • 예를 들어, 1번 집이 5번집보다 높이가 크다면 5번집의 시야를 가린다.
• 이때, 최소한의 집을 부수어서 나머지 집들이 모두 호수를 볼 수 있게 하여라

시간 제한

• 5초

입력

• 테스트케이스 개수 T
  • 1 ≤ T ≤ 100
• 각 테케 별로
  • 집의 개수 N이 주어진다
    • 1 ≤ N ≤ 1000
  • 이후, 집들의 높이가 주어진다
    • 차례대로 서 → 동 순서대로 주어짐
    • 집높이는 항상 1~ 1000이하

출력

• 호수의 경치를 보기위해 부숴야하는 최소 집의 개수는??
  • Cas #x : y 형태로 출력

접근법

• 현재집을 부술 경우, 안 부술 경우 2가지 케이스로 나눌 수 있다.
• 이때, 현재 집을 부수지 않는 경우가 가능 한 조건이 있는데, 이는 이전 집보다 현재집 높이가 클 경우가 부수지 않아도 된다.
• 따라서 2가지 케이스에 따라 모든 케이스를 살펴 보게 되면 2^(1000*1000)가 되므로, 메모이제이션을 통해 최적화를 진행한다.

코드

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

public class Main {
    static int N;
    static int[] arr;
    static int[][] dp = new int[1010][1010];

    static int recur(int cur, int prv) {

        if (cur == N) return 0;

        if (dp[cur][prv] != -1) return dp[cur][prv];

        int ret = 1 << 30;
        // 현재 건물 부수기
        ret = Math.min(ret, recur(cur + 1, prv) + 1);
        // 현재 건물 안 부수기
        if (arr[cur] > prv) ret = Math.min(ret, recur(cur + 1, arr[cur]));

        dp[cur][prv] = ret;
        return ret;
    }

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

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append("Case #").append(tc).append(": ");
            N = Integer.parseInt(br.readLine());
            arr = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            for (int[] d : dp) {
                Arrays.fill(d, -1);
            }
            sb.append(recur(0, 0)).append("\\n");
        }

        System.out.println(sb);
    }
}