📙[Algo] 24.04.03 알고리즘

알고리즘 문제) BOJ 1726. 로봇

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

문제 요약

• 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나
• 로봇 제어 명령어
  • Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
  • Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
• 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점
• 로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성

시간 제한

• 2초

입력

• 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N
  • M과 N은 둘 다 100이하의 자연수
• M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다
• 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향
• 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향
  • 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4
  • 출발지점에서 도착지점까지는 항상 이동이 가능

출력

• 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수

코드

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

// 메모리 초과 이슈
public class Main {
    static int M, N;
    static int[][] arr;
    static int sr, sc, sd, er,ec, ed;
    static boolean[][][] visited;
    // 동북서남 (동1->0 / 서2->2 / 북4->1 / 남3->3)
    static int[] delR = {0, -1, 0, 1};
    static int[] delC = {1, 0, -1, 0};

    static class Node implements Comparable<Node> {
        int row;
        int col;
        int dir;
        int cmd;

        Node(int row, int col, int dir, int cmd) {
            this.row = row;
            this.col = col;
            this.dir = dir;
            this.cmd = cmd;
        }

        @Override
        public int compareTo(Node node) {
            return this.cmd - node.cmd;
        }

    }

    static boolean boundaryCheck(int row, int col) {
        return 0 <= row && 0 <= col && row < M && col < N;
    }

    static int bfs(int row, int col, int dir) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(row, col, dir, 0));
        visited[dir][row][col] = true;

        int cr, cc, cd, cm, nr, nc, nd, size;
        while (!pq.isEmpty()) {
            size = pq.size();

            for (int s = 0; s < size; s++) {
                cr = pq.peek().row;
                cc = pq.peek().col;
                cd = pq.peek().dir;
                cm = pq.poll().cmd;

                if (cr == er && cc == ec && cd == ed) return cm;

                // 명령 1 : Go K (1~3) 해당 방향으로 K만큼 이동
                // 명령 2 : Turn dir (left or right) 각각 왼쪽 또는 오른쪽으로 90도 회전
                /* 나올 수 있는 경우
                   현재 방향으로 +1,+2,+3 이동
                   왼쪽 90도 회전 후 +1,+2,+3 이동 (dir+1)%4
                        동0 -> 북1 / 북1 -> 서2 / 서2 -> 남3 / 남3 -> 동0
                   오른쪽 90도 회전 후 +1,+2,+3 이동 (dir+3)%4
                        동0 -> 남3 / 남3 -> 서2 / 서2 -> 북1 / 북1 -> 동0
                */

                // 회전 안하고 K이동 -> 여기서 주의할 것 -> k만큼 이동하는 과정에서 1이 있으면 안 됨
                for (int i = 1; i <= 3 ; i++) {
                    nr = cr + delR[cd] * i;
                    nc = cc + delC[cd] * i;

                    if (!boundaryCheck(nr,nc) || visited[cd][nr][nc]) continue;

                    if (arr[nr][nc] == 1) break;

                    pq.offer(new Node(nr, nc, cd, cm + 1));
                    visited[cd][nr][nc] = true;
                }

                // 왼쪽 회전
                nd = (cd + 1) % 4;
                if (!visited[nd][cr][cc]) {
                    pq.offer(new Node(cr, cc, nd, cm + 1));
                    visited[nd][cr][cc] = true;
                }

                // 오른쪽 회전
                nd = (cd + 3) % 4;
                if (!visited[nd][cr][cc]) {
                    pq.offer(new Node(cr, cc, nd, cm + 1));
                    visited[nd][cr][cc] = true;
                }
            }
        }
        return 0;
    }

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

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

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

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

        st = new StringTokenizer(br.readLine());
        er = Integer.parseInt(st.nextToken()) - 1;
        ec = Integer.parseInt(st.nextToken()) - 1;
        ed = Integer.parseInt(st.nextToken());

        // 방향 수정한 방식으로 바꿔주기
        if (sd == 1) sd = 0;
        else if (sd == 4) sd = 1;
        if (ed == 1) ed = 0;
        else if (ed == 4) ed = 1;

        visited = new boolean[4][M][N];

        bw.write(String.valueOf(bfs(sr, sc, sd)));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2412. 암벽 등반

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

문제 요약

• 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다
  • 홈의 좌표는 (x, y)와 같이 표현
• |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다
• 홈들을 이용하여 이동하면서 y = T(1 ≤ T ≤ 200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다
• 현재 당신이 있는 위치는 (0, 0)
• 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다
  • x좌표는 아무 것이나 되어도 상관이 없다

시간 제한

• 2초

입력

• 첫째 줄에 n, T
• 다음 n개의 줄에는 각 점의 x, y좌표
  • 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하

출력

• 첫째 줄에 최소 이동 회수를 출력
  • 정상에 오를 수 없으면 -1을 출력

접근법

5 3
1 2
6 3
4 1
3 2
0 2

• (0,0) 에서 이동 가능한 좌표
  • x좌표 : -2~2
  • y좌표 : -2~2
  ⇒ (0,2) 또는 (1,2)로 이동
• (0,2)
  • x : -2~2
  • y : 0~4
  ⇒ (1,2) 이동
• (1,2)
  • x : -1~3
  • y : 0 ~ 4
  ⇒ (3,2) 이동
• (3,2)
  • x : 1~5
  • y : 0~4
  ⇒ (4,1) 이동
• (4,1)
  • x : 2~6
  • y : -1~3
  ⇒ (6,3) 이동 ⇒ 도착!!
• 위 과정에서 바로 (0,0)에서 (1,2)로 이동했다면 총 4번만 이동하면 된다!
• 현재 위치에서 배열에 담겨진 암벽들의 좌표들 중 이동 가능하고, 방문하지 않은 애들만 큐에 담으면서 bfs 돌리기!
• 이떄 y==T인 구간에서 멈추기!

코드

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

public class Main {
    static int N, T;
    static int[][] stones;
    static ArrayList<Integer>[] list;
    static boolean[] visited;

    // N이 50000개까지 가능
    // for문을 전부 탐색하지말고 이동 가능한 부분만 탐색하게 바꾸기

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

        int cy, ci, ny, size, dist = 0;
        while (!q.isEmpty()) {
            size = q.size();

            for (int s = 0; s < size; s++) {
                cy = q.peek()[0];
                ci = q.poll()[1];

                if (cy == T) return dist;

                for (Integer ni : list[ci]) {
                    if (visited[ni]) continue;

                    ny = stones[ni][1];
                    q.offer(new int[]{ny, ni});
                    visited[ni] = true;
                }
            }
            dist++;
        }

        return -1;
    }

    // 이동 가능한 범위 중 가장 작은 인덱스 값 출력
    static int lowerBound(int s, int e, int key) {
        int m;
        int answer = e;

        while (s <= e) {
            m = (s + e) / 2;
            if (stones[m][0] < stones[key][0] - 2) {
                // 현재 중간값의 x가 이동할 수 있는 x값 보다 작은 값일 때
                s = m + 1;
            } else if (stones[key][0] + 2 < stones[m][0]) {
                // 현재 중간값의 x가 이동할 수 있는 x값 보다 큰 값일 떄
                e = m - 1;
            } else {
                // x간 이동이 가능 함
                answer = m;
                // 하지만 이동 가능한 좌표들 중 가장 작은 값을 구할 것이므로
                e = m - 1;
            }
        }
        return answer;
    }

    // 이동 가능한 범위중 가장 큰 인덱스값 출력
    static int upperBound(int s, int e, int key) {
        int m;
        int answer = e;

        while (s <= e) {
            m = (s + e) / 2;
            if (stones[m][0] < stones[key][0] - 2) {
                // 현재 중간값의 x가 이동할 수 있는 x값 보다 작은 값일 때
                s = m + 1;
            } else if (stones[key][0] + 2 < stones[m][0]) {
                // 현재 중간값의 x가 이동할 수 있는 x값 보다 큰 값일 떄
                e = m - 1;
            } else {
                // x간 이동이 가능 함
                answer = m;
                // 하지만 이동 가능한 좌표들 중 가장 작은 값을 구할 것이므로
                s = m + 1;
            }
        }
        return answer;
    }

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

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

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

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

        // x좌표 기준 정렬
        Arrays.sort(stones, (o1, o2) -> {
            if(o1[0] == o2[0]) return o1[1] - o2[1];
            else return o1[0] - o2[0];});

        // 위 두 범위를 모두 충족하는 좌표만 리스트에 담기
        int lowerX, upperX;
        for (int i = 0; i <= N; i++) {
            lowerX = lowerBound(0, N, i);
            upperX = upperBound(0, N, i);

            for (int j = lowerX; j <= upperX ; j++) {
                if (Math.abs(stones[i][1] - stones[j][1]) <= 2) {
                    list[i].add(j);
                }
            }
        }

        visited = new boolean[N + 10];

        bw.write(String.valueOf(bfs(0, 0)));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 13910. 개업

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

문제 요약

• 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성
  • 조건 → ex) 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.

시간 제한

• 1초

입력

• 첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤100)
• 두 번째 줄에는 웍의 크기 Si(1≤Si≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다

출력

• 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력
• 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력

접근법

8 1 4 5

⇒ 무조건 큰 걸로 나누면 안됨

⇒ bfs

⇒ 동시에 여러 웍으로 요리 가능하니까 주의 ⇒ 시간초과 뜰까 무작정 투포인터 갈기지 말기

코드

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

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

    static int bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        int cnt = 0, cur, nxt, size, s, e;
        while (!q.isEmpty()) {
            size = q.size();

            for (int i = 0; i < size; i++) {
                cur = q.poll();

                if (cur == N) return cnt;

                // 웍을 동시에 사용할 수 있음 -> 주의
                for (int j = 0; j < M; j++) {
                    for (int k = 0; k < M; k++) {
                        nxt = j == k ? cur + arr[j] : cur + arr[j] + arr[k];

                        if (10000 < nxt || visited[nxt]) continue;
                        if (N < nxt) continue;

                        q.offer(nxt);
                        visited[nxt] = true;
                    }
                }
            }
            cnt++;
        }

        return -1;
    }

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

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

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

        visited = new boolean[10010];

        Arrays.sort(arr);

        bw.write(String.valueOf(bfs(0)));
        bw.flush();
        bw.close();
        br.close();
    }
}