📙[Algo] 24.08.18 알고리즘

알고리즘 문제) BOJ 16469. 소년 점프

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

문제 요약

• 마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다.
• 뒤늦게 미로에 도착한 악당 무리 3명는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다.
  • 악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다.
  • 또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다.
• 악당은 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신
• R*C 크기의 미로가 주어지고, 악당들의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 되는 지점을 마미손에게 알려주자

시간 제한

• 1초

입력

• 첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다
  • 2 ≤ R, C ≤ 100
• 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다
  • 숫자 0은 이동 가능한 길, 1은 벽을 나타낸다
• 그 다음 줄부터 3개의 줄은 악당의 위치(행, 열)를 나타내는 자연수 Xi, Yi가 (1 ≤ Xi ≤ R, 1 ≤ Yi ≤ C)주어진다
  • 악당들은 위치가 겹치지 않고, 항상 이동 가능한 길에서 출발한다
  • 맨 왼쪽 위의 위치는 (1, 1)이다

출력

• 첫째 줄에 한 지점에 세 악당이 모일 때 걸린 시간의 최소 값을 출력
• 둘째 줄에는 그러한 지점의 개수를 출력
• 만약 세 악당이 모일 수 있는 지점이 존재하지 않는다면 -1를 출력

접근법

• 세 악당이 한 칸에 집합할 수 있는 최단 경로를 찾기 위해 bfs 알고리즘을 사용했다
• 각 악당의 번호 (0 ~ 2)와 각 악당의 위치를 큐에 담았고, 방문체크를 할 때도 각 악당별로 방문체크를 하기 위해 3차원 배열을 사용했다
• 최단 시간을 찾기 위해 bfs를 돌릴 때, 큐 사이즈만큼씩 돌리고나서 time변수를 + 1 해주었다.
• 또한, 3명의 악당이 집합한 개수를 확인하기 위한 2차원 배열 cnt를 선언했고, 각 악당이 이동할 때마다 해당 위치에 존재하는 악당 숫자를 카운팅했다.
  • 이때 cnt[row][col]값이 3이 되는 경우, 모든 악당이 모였다는 의미이므로 따로 flag변수를 이용해 true값으로 선언했다.
  • 또한, 가능한 경우의 개수도 구해야해서 total변수에 + 1해주었다.
• 한번 큐를 돌고 나서, 만약 flag가 true일 경우, 한 곳에 집합하는 경우를 찾은 것이므로, 그때 까지 소모한 시간 time과 그런 경우의 총 개수인 total을 반환시켰다.

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static int[][] cnt;
    static int[][] pos;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static int[] bfs() {
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] visited = new boolean[3][N][M];
        for (int i = 0; i < 3; i++) {
            q.offer(new int[]{i, pos[i][0], pos[i][1]});
            visited[i][pos[i][0]][pos[i][1]] = true;
        }

        int no, cr, cc, mr, mc, size, time = 0, total = 0;
        boolean flag = false;
        while (!q.isEmpty()) {
            size = q.size();

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

                cnt[cr][cc]++;

                if (cnt[cr][cc] == 3) {
                    flag = true;
                    total++;
                }

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

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

                    visited[no][mr][mc] = true;
                    q.offer(new int[]{no, mr, mc});
                }
            }
            if (flag) return new int[] {time, total};
            time++;
        }

        return new int[]{-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());

        arr = new int[N][M];
        cnt = new int[N][M];
        pos = new int[3][2];

        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = input.charAt(j) - '0';
            }
        }

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            pos[i][0] = Integer.parseInt(st.nextToken()) - 1;
            pos[i][1] = Integer.parseInt(st.nextToken()) - 1;
        }

        int[] ans = bfs();

        if (ans[0] == -1) {
            System.out.println(-1);
        } else {
            System.out.println(ans[0]);
            System.out.println(ans[1]);
        }
    }
}

 

알고리즘 문제) BOJ 28017. 게임을 클리어하자

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

문제 요약

• 게임은 여러 회차가 존재하며, 무기도 여러가지가 존재한다
• 이때, 한 회차를 클리어 할 때는, 무기를 도중에 바꾸지 않고 게임을 진행한다
• 또한, 여러 회차를 진행할 때, 이전 무기는 또 사용하지 않는다
• 게임 회차별로, 각 무기를 사용할 때 클리어하는 시간도 다르다
• 최선의 무기를 선택해 최대한 빨리 게임을 끝나는 방법을 찾아라

시간 제한

• 1초

입력

• 게임을 몇 회차 하는지 나타내는 수 N과 무기 종류 M이 주어진다
  • 2 ≤ N, M ≤ 500
• 둘째줄부터 N개의 줄에 각 무기별 게임을 클리어하는 시간 t1, .. , tN이 주어진다.
  • 1 ≤ ti ≤ 1만

출력

• 회차마다 효율적인 무기를 선택하였을 때 총 클리어 시간의 최솟값을 출력

접근법

• dp[cur][pre] : 현재 게임가 cur이고 이전 무기로 pre를 사용했을 때, 얻을 수 있는 최소 비용을 저장
• 각 회차별 이전과 중복되지 않을 무기를 선택했을 때의 모든 케이스를 탐색하고, 중복 케이스 처리를 위해 dp배열을 통해 메모이제이션
  • 함수는 게임을 클리어했을 때의 총 소모 시간을 반환하며, 최종적으로 가장 최소 시간을 반환하게 된다.

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static int[][] dp;

    static int dfs(int cur, int pre) {
        if (cur == N) return 0;

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

        int ret = 1 << 30;
        for (int i = 1; i <= M; i++) {
            if (pre == i) continue;
            ret = Math.min(ret, dfs(cur + 1, i) + arr[cur][i]);
        }

        dp[cur][pre] = ret;
        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());

        arr = new int[N][M + 1];

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

        dp = new int[N][M + 1];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }

        int ans = dfs(0, 0);
        System.out.println(ans);
    }
}