📙[Algo] 24.07.03~07.05 알고리즘

알고리즘 문제) BOJ 5913. 준규와 사과

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

문제 요약

• 5*5 크기의 과수원이 존재하며, 가장 왼쪾 위 칸은 (1,1), 가장 오른쪽 아래 칸은 (5,5)이다.
• 이때 구역 k개를 제외한 구역에 사과 나무가 하나씩 존재한다
• 준규는 (1,1)에서 사과를 수확, 해빈이는 (5,)에서 수확을 시작
• 이때, 인접한 칸 중 사과 나무가 있는 칸으로 이동한다.
• 준규와 해빈이는 모든 사과를 수확하고 마지막에 같은 칸에서 만나려고 한다.
• 이때, 사과를 수확하는 방법의 수를 구해라
• 수학을 마친 칸으로는 다시 이동하지 않는다.
• 또, 마지막을 제외하고 같은 칸에서 만날 수 없다.

시간 제한

• 1초

입력

• k ( 0 ≤ k ≤ 22, 짝수)
• k개줄에는 사과 나무가 없는 칸의 위치가 주어짐 (i, j)

출력

• 사과를 모두 수확하는 방법의 수를 출력

접근법

• 백트랙킹 돌며, 준규와 해빈이의 위치 (jr,jc) (hr,hc) ,남은 사과나무 개수 remain을 매개변수로 넘겨주었다.
• 이때 둘의 위치가 같을 떄, remain값이 1보다 작을 때 1을 반환시켰고, 그게 아니면 0을 반환 시켰다.
  • 마지막칸을 제외하고 같은 칸에서 만날 수 없으므로
• 또한 2중 for문으로 준규와 해빈이의 위치를 이동시키며 나올 수 있는 모든 경우를 탐색
  • 이때, 경계 안에서 방문체크와 사과나무가 있는칸(0)만 탐색했고, return값을 ret변수에 누적해서 더했다.

코드

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

public class Main {
    static int K;
    static int[][] arr = new int[5][5];
    static boolean[][] visited = new boolean[5][5];
    static int[] delR = {0, 0, -1, 1};
    static int[] delC = {-1, 1, 0, 0};


    static int recur(int jr, int jc, int hr, int hc, int remain) {
        if (jr == hr && jc == hc) {
            // 모든 사과를 수확하고 도착 위치가 같다면
            if (remain < 1) {
                return 1;
            }
            else return 0;
        }

        int ret = 0;

        int mjr, mjc, mhr, mhc;
        for (int jd = 0; jd < 4; jd++) {
            for (int hd = 0; hd < 4; hd++) {
                mjr = jr + delR[jd];
                mjc = jc + delC[jd];
                mhr = hr + delR[hd];
                mhc = hc + delC[hd];

                if (mjr < 0 || mjc < 0 || mhr < 0 || mhc < 0
                        || 5 <= mjr || 5 <= mjc || 5 <= mhr || 5 <= mhc) continue;

                if (visited[mjr][mjc] || visited[mhr][mhc]) continue;
                if (arr[mjr][mjc] == 1 || arr[mhr][mhc] == 1) continue;

                visited[mjr][mjc] = true;
                visited[mhr][mhc] = true;
                ret += recur(mjr, mjc, mhr, mhc, remain - 2);

                visited[mjr][mjc] = false;
                visited[mhr][mhc] = false;
            }
        }

        return ret;
    }

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

        K = Integer.parseInt(br.readLine());

        int r, c;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken()) - 1;
            c = Integer.parseInt(st.nextToken()) - 1;

            arr[r][c] += 1;
        }

        visited[0][0] = true;
        visited[4][4] = true;

        int ans = recur(0, 0, 4, 4, 25 - K - 2);
        System.out.println(ans);
    }
}

 

알고리즘 문제) BOJ 17244. 아맞다우산

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

문제 요약

• N * M 맵이 존재
• 해당 맵의 값은 다음과 같이 주어진다
  • . : 빈칸
  • # : 벽 -> 이동 불가
  • S : 시작 위치
  • E : 도착 위치
  • X : 챙겨야할 물건
• S에서 출발하여 물건을 모두 챙기고 E에 가장 빠르게 도착할떄까지 걸리는 시간?

시간 제한

• 1초

입력

• 가로 길이 N과 세로 길이 M
  • 3 ≤ N, M ≤ 50
• M개의 줄에 집의 구조가 주어짐
  • 챙겨야할 물건은 최대 5개까지 가능
  • 집은 언제나 벽으로 둘러싸여 있으며, 도착지는 무조건 하나

출력

• S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력
  • 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

접근법

• bfs + 비트마스킹
• 처음 지도를 입력 받을 때, 문자를 숫자로 변환했다

  • → -1

  • . → 0
  • S → 0 & 시작 위치 저장 (sr, sc)
  • E → 0 & 도착 위치 저장 (er, ec)
  • X → 1부터 하나씩 증가시킴
    • 만약 물건이 5개있다면 물건마다 1~5까지 번호가 부여되며, 해당 번호가 지도에 기록된다.
• bfs로 S부터 E까지 모든 물건을 챙기고 최단 경로로 이동해야 하므로 bfs알고리즘을 사용
  • 이때, 현재까지 어떤 물건을 선택했느냐에 따라 케이스가 나뉘므로
    • 방문체크 배열을 3차원으로 선언하여, 현재 위치와 지금까지 선택한 물건 상태값을 기준으로 체크했다.
      • 이때 물건을 선택한 상태는 비트마스킹으로 저장
        • 어차피 물건은 최대 5개까지만 주어짐
• 만약 물건을 다 선택하고 & 도착지에 도착했다면 그때 걸린 시간을 출력했다.

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static int sr, sc, er, ec, idx;
    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<>();
        visited = new boolean[M][N][1 << 6];
        q.offer(new int[]{sr, sc, 0});
        visited[sr][sc][0] = true;

        int cr, cc, cs, mr, mc, bit, size, time = 0;
        while (!q.isEmpty()) {
            size = q.size();

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

                if (cr == er && cc == ec && cs == (1 << (idx + 1)) - 2) {
                    return time;
                }

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

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

                    if (arr[mr][mc] == 0) {
                        q.offer(new int[]{mr, mc, cs});
                        visited[mr][mc][cs] = true;
                    } else if (arr[mr][mc] > 0) {
                        bit = cs | (1 << arr[mr][mc]);
                        q.offer(new int[]{mr, mc, bit});
                        visited[mr][mc][bit] = true;
                    }
                }
            }
            time++;
        }

        return time;
    }

    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[M][N];
        String input;
        char ch;
        for (int i = 0; i < M; i++) {
            input = br.readLine();
            for (int j = 0; j < N; j++) {
                ch = input.charAt(j);

                if (ch == 'S') {
                    arr[i][j] = 0;
                    sr = i;
                    sc = j;
                } else if (ch == 'E') {
                    arr[i][j] = 0;
                    er = i;
                    ec = j;
                } else if (ch == '#') {
                    arr[i][j] = -1;
                } else if (ch == '.') {
                    arr[i][j] = 0;
                } else if (ch == 'X') {
                    arr[i][j] = ++idx;
                }
            }
        }
        System.out.println(bfs());
    }
}

 

알고리즘 문제) BOJ 1102. 발전소

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

문제 요약

• 발전소 일부가 고장났다
• 이때 고장나지 않은 발전소를 이용해 고장난 발전소를 고쳐서, 최소 P개의 발전소가 고장나지 않도록하자
• 이때, 발전소를 고치는 최소 비용은?

시간 제한

• 2초

입력

• 발전소 개수 N
  • N ≤ 16, 자연수
• N개의 줄에 발전소 i를 통해 j를 재시작할 때 드는 비용(i, j)이 주어진다. → 36이하의 양수
• 그 다음 줄에는 각 발전소가 켜져 있으며 Y, 꺼져있으면 N이 순서대로 주어진다 ex) YNNN
• 마지막 줄에는 P가 주어지며, N이하의 자연수이다

출력

• 정답 출력
  • 불가능하면 -1 출력

접근법

• 비트마스킹 + dp문제
• 발전소 상태를 String 값으로 입력 받게 되는데, 나중에 비트로 고장 여부를 확인해야해서 따로 처리
  • StringBuilder를 사용해 ‘Y’인 경우 1을 추가했고, ‘N’인 경우 0을 추가했다.
  • 이렇게 되면 1번 발전소 상태값이 가장 앞에 가게 되는데, 비트 변환시 1번값이 이 가장 뒤로 가야하므로 reverse() 함수 사용 후, parseInt함수로 2진수 변환했다
  • 그러면 현재 발전소 상태값이 2진수형태로 기록
• 또한, 최소 P개의 발전소만 고장나지 않으면 되므로, 앞에서 ‘Y’를 만날때마다 1씩 감소시킨다.
  • 이때, P가 음수면 더이상 고칠 필요 없으며 0을 출력,
  • 그게 아닐 경우 재귀를 돌려 최소 비용을 구했따.
• 재귀 함수에 매개변수로 remain과 state값을 넘겼고,.
  • remain은 고쳐야할 남은 공장 수
  • state값은 지금까지 고친 공장 상태값을 기록했다.
  • 어떤 공장이 어떤 공장을 고쳤는지에 따라 경우가 나뉘어서, 재귀 안에서 2중 for문을 돌렸다(N이 16이하라 시간 터질 우려 X)
    • 외부 for문에서 고장나지 않은 공장만 찾은 후,
    • 내부 for문에서 고장난 공장만 선택하게 끔했다.
      • 이때, 재귀 호출 시 state값은 비트마스킹으로 고친 공장까지 반영해서 넘겼다.
• 메모이제이션
  • dp[remain][state] : 고쳐야 할 공장 수가 remain개 이고, 고친 공장 상태 값이 state일 때 최소 비용

코드

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

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

    static int recur(int remain, int state) {
        if (remain == 0) return 0;

        if (dp[remain][state] != -1) return dp[remain][state];

        int ret = 1 << 30;
        for (int i = 0; i < N; i++) {
            if ((state & (1 << i)) == 0) continue;

            for (int j = 0; j < N; j++) {
                if ((state & (1 << j)) != 0) continue;

                ret = Math.min(ret, recur(remain - 1, state | (1 << j)) + arr[i][j]);

            }
        }

        dp[remain][state] = ret;
        return ret;
    }

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

        N = Integer.parseInt(br.readLine());

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

        String str = br.readLine();
        min = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == 'Y') {
                min--;
                sb.append("1");
            }
            else sb.append("0");
        }
        sb.reverse();
        int curBit = Integer.parseInt(sb.toString(), 2);

        dp = new int[20][ 1 << 17];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }

        if (min < 0) System.out.println(0);
        else {
            int ans = recur(min, curBit);

            if (ans == 1 << 30) System.out.println(-1);
            else System.out.println(ans);
        }

    }
}

 

알고리즘 문제) BOJ 5972. 택배 배송

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

문제 요약

• N개의 헛간, M개의 양방향 길
• 각각의 길에는 Ci마리의 소가 존재
• 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.
• 현서는 찬홍이에게 가면서 지나가는 길에 소를 만나면 여물을 줘야 할 때, 최소 여물은 얼마일까?

시간 제한

• 1초

입력

• N과 M
  • 1 ≤ N ≤ 50,000
  • 1 ≤ M ≤ 50,000
• 둘째 줄부터 M+1번째 줄까지 세 개의 정수 Ai, Bi, Ci
  • 헛간 Ai, Bi, 소 마리수 Ci
  • 1 ≤ Ai ≤ N
  • 1 ≤ Bi ≤ N
  • Ai != Bi

출력

• 농부 현서가 가져가야 될 최소 여물

접근법

• 다익스트라 알고리즘

코드

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

public class Main {
    static int N, M;
    static ArrayList<Node>[] lst;
    static int[] dist;
    static boolean[] visited;

    static class Node implements Comparable<Node> {
        int to;
        int cost;

        Node(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }

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

    static void daijk(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.add(new Node(start, 0));

        int cur, nxt, nc;
        while (!pq.isEmpty()) {
            cur = pq.poll().to;

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : lst[cur]) {
                nxt = node.to;
                nc = dist[cur] + node.cost;

                dist[nxt] = Math.min(dist[nxt], nc);

                pq.offer(new Node(nxt, dist[nxt]));
            }
        }
    }

    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());

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

        int a, b, c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            lst[a].add(new Node(b, c));
            lst[b].add(new Node(a, c));
        }

        dist = new int[N + 1];
        Arrays.fill(dist, 1 << 30);
        visited = new boolean[N + 1];

        daijk(1);

        System.out.println(dist[N]);
    }
}