📙[Algo] 24.05.22 알고리즘

📙 Algorithm Solving/Java

📙[Algo] 24.05.22 알고리즘

혜덕hyeduck 2024. 5. 23. 01:23

알고리즘 문제) BOJ 4991. 로봇 청소기

링크 : https://www.acmicpc.net/problem/4991

문제 요약

H*W크기 방이 존재하고, 다음과 같이 맵정보가 주어짐
- . : 깨끗한 칸
- - : 더러운 칸
- x : 가구
- o : 로봇 청소기 시작 위치
이때, 더러운 칸을 모두 꺠끗한 칸으로 만드는데 필요한 이동 횟수 구하기
- 로봇은 같은 칸을 여러번 방문 가능

시간 제한

1초

입력

여러 테스트케이스로 이루어져 있으며 마지막에 0 0이 주어지면 종료
각 테스트케이스 별로
- 첫쨰 줄 : 가로크기 W, 세로크기 H
  - 1 ≤ W,H ≤ 20
- 둘째줄부터 H개 줄에 방의 정보가 주어짐
  - 더러운 칸은 10개를 넘지 않으며, 로봇 청소기 개수는 항상 1개

출력

테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수 최솟값 출력
만약 불가능하다면 -1 출력

접근법

이동 횟수의 최솟값을 구하는문제라서 bfs로 접근
여기에 로봇은 방문한 곳을 또 방문하는 것이 가능하며, 청소 상태에따라 여러 케이스가 존재한다고 생각 → 방문체크 배열을 3차원 형태로 만듬
- 이때 청소 상태는 비트마스킹으로 기록
  - 처음 맵 정보를 입력 받을 때 ‘’ 더러운 곳을 만난 경우 ‘’대신 몇번째 만난 쓰레기 값인지 저장 ⇒ 그러면 각 쓰레기별로 번호가 배정됨
  - 그다음 bfs 돌리면서 쓰레기를 만날 때 해당 map[mr][mc]값을 가져와서 그 값만큼 << 연산을 취한 후 현재까지 청소 상태 값에 OR 연산해서 갱신
    - trash | 1 << (arr[mr][mc] - '0’

코드

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

public class Main {
    static int W, H;
    static char[][] arr;
    static int robotR, robotC;
    static int trashCnt;
    static boolean[][][] visited;
    static Queue<int[]> q = new LinkedList<>();
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};


    static int bfs() {
        q.offer(new int[]{robotR, robotC, 0});
        visited[robotR][robotC][0] = true;

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

            size = q.size();

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

                if (trash == (1 << trashCnt) - 1) {
                    q.clear();
                    return move;
                }

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

                    if (mr < 0 || mc < 0 || H <= mr || W <= mc || arr[mr][mc] == 'x') continue;

                    if (arr[mr][mc] != '.') {
                        // 쓰레기 만난 경우

                        // 방문 체크
                        if (visited[mr][mc][trash | 1 << (arr[mr][mc] - '0')]) continue;

                        visited[mr][mc][trash | 1 << (arr[mr][mc] - '0')] = true;
                        q.offer(new int[]{mr, mc, trash | 1 << (arr[mr][mc] - '0')});
                    } else {
                        // 빈 공간인 경우

                        //방문 체크
                        if (visited[mr][mc][trash]) continue;

                        visited[mr][mc][trash] = true;
                        q.offer(new int[]{mr, mc, trash});
                    }
                }
            }

            move++;
        }

        return -1;
    }


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

        StringBuilder sb = new StringBuilder();
        String input;
        while (true) {
            st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            if (W == 0 && H == 0) break;

            arr = new char[H][W];
            trashCnt = 0;
            for (int i = 0; i < H; i++) {
                input = br.readLine();
                for (int j = 0; j < W; j++) {
                    arr[i][j] = input.charAt(j);

                    if (arr[i][j] == '*'){
                        arr[i][j] = Integer.toString(trashCnt++).charAt(0);
                    } else if (arr[i][j] == 'o') {
                        robotR = i;
                        robotC = j;
                        arr[i][j] = '.';
                    }
                }
            }

            visited = new boolean[H][W][1 << (trashCnt + 1)];
            sb.append(bfs()).append("\n");
        }

        System.out.println(sb);

        br.close();
    }
}

알고리즘 문제) BOJ 11003. 최솟값 찾기

링크 : https://www.acmicpc.net/problem/11003

문제 요약

N개의 수 A1,… , An과 L이 주어진다.
이때 Di = Ai-L+1 ~ Ai 중 최솟값일 때, D에 저장된 수 출력
- 이때 i ≤ 0인 경우는 무시하고 D를 구함

시간 제한

2.4초

입력

N L
- 1 ≤ L ≤ N ≤ 500만
N개의 수 Ai가 주어진다.
- -10억 ≤ Ai ≤ 10억

출력

Di를 공백으로 구분하여 출력

접근법

만약 N=12, L=3일때
- D1 = A1-3+1 ~ A1 ⇒ A1
- D2 = A2-3+1 ~ A2 ⇒ A1~A2
- D3 = A3-3+1 ~ A3 ⇒ A1~A3
- D4 = A4-3+1 ~ A4 ⇒ A2~A4
⇒ Ai까지 L개씩 조회
deq에는 앞에서부터 가장 작은 값들이 차례대로 저장되도록 한다.
현재 원소 기준 L개씩 조사하는 것이므로 가장 앞에있는 deq의 인덱스가 L범위를 벗어나면 해당 원소는 제거
deq에 저장된 원소들중 현재 원소보다 큰게 있다면 계속 제거
- 여기서 중간에 현재 원소보다 작은 원소를 발견하면 break문 걸어야함 → 안걸면 계속 전체 탐색하므로 시간초과
deq에 마지막원소로 현재 원소 추가
출력문에 현재 deq의 가장 앞 원소 넣기 → L범위 내 가장 작은 원소의미

코드

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


public class Main {

    static class Num {
        int no;
        int idx;

        Num(int no, int idx) {
            this.no = no;
            this.idx = idx;
        }
    }

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

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

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

        Deque<Num> deq = new ArrayDeque<>();
        deq.offer(new Num(arr[1], 1));
        StringBuilder sb = new StringBuilder();
        sb.append(arr[1]).append(" ");
        int size;
        for (int i = 2; i <= N; i++) {
            // 가장 앞에 있는 원소의 인덱스가 L범위를 벗어나면 제거
            if (!deq.isEmpty() && deq.peekFirst().idx < i - L + 1) deq.removeFirst();

            // 만약 덱에 가장 뒤에있는 원소부터 탐색하면서 현재 원소보다 큰 값들은 제거
            size = deq.size();
            while (size > 0) {
                if (!deq.isEmpty() && deq.peekLast().no >= arr[i]) deq.removeLast();
                else break;
                size--;
            }

            // 덱에 현재 원소 넣기
            deq.addLast(new Num(arr[i], i));

            sb.append(deq.peekFirst().no).append(" ");
        }

        System.out.println(sb);

        br.close();
    }
}

알고리즘 문제) BOJ 1029. 그림 교환

링크 : https://www.acmicpc.net/problem/1029

문제 요약

그림을 서로 거래 할 때 다음 조건을 충족하며 거래
- 그림을 산 가격보다 크거나 같은 가격으로 팔 것
- 같은 그림을 두 번 이상 사지 말 것
이때, 1번 아티스트가 외부 상인으로부터 그림을 0원 주고 살때, 그 그림으로 다른 사람들에게 팔려고 한다.
이때, 그림을 소유했던 사람 수의 최댓값을 출력

시간 제한

2초

입력

예술가의 수 N
- 2 ≤ N ≤ 15
둘째줄부터 N개 줄에 N개의수가 주어짐
- i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에게 그 그림을 살 때의 가격
- 가격은 0~9

출력

첫째 줄에 그 그림을 소유 했던 사람들 (잠시라도 소유했던 사람도 포함)의 최댓값을 출력

접근법

dp + 비트마스킹
dp → 현재 그림 소유한 화가 번호, 그림 소유 상태, 이전 거래 가격을 기준으로 가장 최대로 소유한 사람들 수 저장
이때 이미 소유한 사람을 또 선택하거나, 거래가격이 이전가격보다 낮은 경우는 pass

코드

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


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

    static int recur(int prv, int selected, int prvPrice) {

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

        int ret = 0;
        for (int i = 0; i < N; i++) {
            if ((selected & 1 << i) != 0) continue;
            if (prvPrice > arr[prv][i]) continue;

            ret = Math.max(recur(i, selected | 1 << i, arr[prv][i]) + 1, ret);
        }

        dp[prv][selected][prvPrice] = 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());

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

        dp = new int[N + 1][1 << (N + 1)][10];
        for (int[][] d1 : dp) {
            for (int[] d2 : d1) {
                Arrays.fill(d2, -1);
            }
        }

        System.out.println(recur(0,1, 0) + 1);

        br.close();
    }
}