📙[Algo] 24.05.22 알고리즘

알고리즘 문제) 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();
    }
}