📙[Algo] 24.05.17~19 알고리즘

알고리즘 문제) BOJ 1311. 할 일 정하기 1

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

문제 요약

• N명의 사람과 N개의 일이 존재
  • 모든 일을 하나씩 담당해야 함
  • 각 일을 담당하는 사람은 오직 한 명
• 1번부터 N번까지 사람과 일에 번호가 매겨져 있음
• Dij : i번 사람이 j번 일을 할 때 필요한 비용
• 이때, 모든 일을 하는데 필요한 비용의 최솟값 구하기

시간 제한

• 1초

입력

• 사람과 일의 수 N
  • 1 ≤ N ≤ 20
• 둘째 줄부터 N개의 줄에 D의 내용이 주어짐
  • 비용은 1만 이하 자연수

출력

• 모든 일을 하는데 필요한 비용의 최솟값

접근법

• 탑다운 dp + 비트마스킹
  • 1번째 사람부터 일을 선택하면서, 최종적으로 N번째 사람이 일을 선택할 때 가장 적은 비용을 반환
  • 이전에 선택한 일의 상태에 따라 다른 결과값을 갖게 되므로, dp에 사람 번호와 이전까지 선택한 일 번호 상태값을 기반으로 메모
• dp[cur][selected]
  • cur : 사람 번호
  • selected : 이전까지 선택한 일 번호 기록 → 비트마스크

코드

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


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

    static int recur(int cur, int selected) {

        if (cur == N + 1) return 0;

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

        int ret = 1 << 30;
        for (int i = 1; i <= N; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            ret = Math.min(ret, recur(cur + 1, selected | 1 << i) + arr[cur][i]);
            visited[i] = false;
        }

        dp[cur][selected] = 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 + 1][N + 1];

        visited = new boolean[N + 1];

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

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

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

알고리즘 문제) BOJ 2098. 외판원 순회

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

문제 요약

• 1번부터 N번까지 번호가 매겨진 도시들이 있고, 도시들 사이에 길이 있다.
• 어느 한 도시에서 출발해 N개의 도시를 모 두 거쳐 다시 원래 도시로 돌아오는 순회 경로를 계획하려고 한다.
  • 한 번 갔던 도시로 또 갈 수 없다(맨 마지막에 출발지로 돌아오는 경우는 제외)
  • 이때 가장 적은 비용을 들이는 여행 계획을 세우려고한다.
• 각 도시간 이동하는 데 드는 비용은 W[i][j]로 주어진다
  • W[i][j] : 도시 i에서 j로 가기 위한 비용
    • 그러나 W[i][j]는 W[j][i]와 다를 수 있다.
    • W[i][i]는 항상 0이다
    • 도시 i에서 j로 갈 수 없는 경우도 W[i][j]=0이댜
• N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 경로 구하기

시간 제한

• 1초

입력

• 도시 수 N
  • 2 ≤ N ≤ 16
• N개의 줄에 비용행렬이 주어진다.
  • 원소 값은 100만이하 양수
  • 항상 순회할 수 있는 경우만 입력으로 주어진다

출력

• 외판원 순회에 필요한 최소 비용 출력

접근법

• 탑다운 dp + 비트마스킹
• for문으로 출발지를 start변수에 지정하고 함수의 반환값이 가장 최소인 것을 찾는다.
• dp[start][prv][selected]
  • start : 출발지 번호
  • prv : 이전에 방문한 노드
  • selected : 지금까지 방문한 노드 상태값
  ⇒ 각 상태에 따라 가장 최소 비용을 dp에 저장
• 방문 체크와 selected 상태값을 비트마스킹 해서 진행
  • 방문 체크 : selected & (1 << i)) != 0 → 이미 방문한 경우므로 pass
  • 가지 치기 : W[prv][i]값이 0인 경우 경로가 없는 경우므로 pass
• 기저 조건
  • selected == (1 << (N + 1)) - 2 ⇒ 모든 노드를 방문한 경우
  • W[prv][start]가 0인 경우 경로가 없으므로 가장 큰 값 반환
  • 그게 아닐 경우 W[prv][start]값 반환

코드

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

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

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

        if (selected == (1 << (N + 1)) - 2) {
            if (W[prv][start] == 0) return  1 << 30;
            return W[prv][start];
        }

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

        int ret = 1 << 30;
        for (int i = 1; i <= N; i++) {
            if ((selected & (1 << i)) != 0 || W[prv][i] == 0) continue;

            ret = Math.min(ret, recur(start, i, selected | (1 << i)) + W[prv][i]);
        }

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

        W = new int[N + 1][N + 1];

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

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

        int ans = 1 << 30;
        for (int i = 1; i <= N; i++) {
            ans = Math.min(ans, recur(i, i, 1 << i));
        }

        System.out.println(ans);

        br.close();
    }
}

알고리즘 문제) BOJ 16933. 벽 부수고 이동하기 3

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

문제 요약

• N*M 행렬의 맵이 존재
  • 0 : 이동 가능한 공간
  • 1 : 벽(이동X)
• (1,1)에서 (N,M)위치까지 최단 경로로 이동하려고 함
  • 가장 적은 개수의 칸을 지남
    • 시작칸과 끝칸도 포함
• 단, 한 번 이동할 때마다 낮, 밤이 바뀐다.
  • 같은 칸에 머무를 때도 바뀐다.
• 벽은 K개까지 부수고 이동할 수 있으며, 낮에만 부술 수 있다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우 인접 칸이다.
• 최단 거리 구하기

시간 제한

• 2초

입력

• N, M, K
  • 1≤N≤1000
  • 1≤M≤1000
  • 1≤K≤10
• N개의 줄에 M개의 숫자로 맵이 주어짐
  • (1,1)과 (N,M)은 항상 0

출력

• 첫째줄에 최단 거리 출력
  • 불가능하면 -1

접근법

• 기존 벽부수기 문제 해결했다면 쉽게 풀수 있던 문제인데,
• 계속 시간초과, 메모리초과 뜬 이유를 생각해보았다.
  • 이전에는 visited체크를 visited[mr][mc][crush]하나로만 체크를 하고 넘겼던게 문제였다.
  • 각 조건마다 방문체크를 다르게 하니까 그에맞게, 방문체크도 다르게 해야했음 ⇒ 주의!!!

코드

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


public class Main {
    static int N, M, K;
    static int[][] map;
    static boolean[][][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static class Node{
        int row;
        int col;
        int crush;
        int isNight;
        int moveCnt;

        Node(int row, int col, int crush, int isNight, int moveCnt) {
            this.row = row;
            this.col = col;
            this.crush = crush;
            this.isNight = isNight;
            this.moveCnt = moveCnt;
        }
    }
    static int bfs(int row, int col) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(row, col, 0, 0, 1));
        visited[row][col][0] = true;

        int cr, cc, mr, mc, crush, isNight, moveCnt, size;
        while (!q.isEmpty()) {

            size = q.size();

            for (int s = 0; s < size; s++) {
                cr = q.peek().row;
                cc = q.peek().col;
                crush = q.peek().crush;
                isNight = q.peek().isNight;
                moveCnt = q.poll().moveCnt;

                if (cr == N - 1 && cc == M - 1) {
                    return moveCnt;
                }

                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 (map[mr][mc] == 1) {
                        // 벽이라면
                        if (isNight == 0 && crush < K && !visited[mr][mc][crush + 1]) {
                            // 낮이고 부순 벽이 K보다 작다면 부숨
                            visited[mr][mc][crush + 1] = true;
                            q.offer(new Node(mr, mc, crush + 1, 1, moveCnt + 1));
                        } else if (isNight == 1 && crush < K) {
                            // 밤이고 부순 벽이 K보다 작다면 부수진 않고 제자리에 기다리기
                            visited[cr][cc][crush] = true;
                            q.offer(new Node(cr, cc, crush, 0, moveCnt + 1));
                        }
                    } else {
                        // 빈공간이라면 그냥 이동
                        if (!visited[mr][mc][crush]) {
                            visited[mr][mc][crush] = true;
                            q.offer(new Node(mr, mc, crush, (isNight + 1) % 2, moveCnt + 1));
                        }
                    }
                }
            }
        }

        return -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());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M][K + 1];

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

        System.out.println(bfs(0, 0));
    }
}

알고리즘 문제) BOJ 2638. 치즈

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

문제 요약

• N*M 모눈종이 위에 치즈가 있음
• 치즈는 외부 공기와 2변 이상이 접촉하면, 1시간만에 녹음
• 단, 내부에 있는 공간은 외부 공기와 접촉하지 않으므로, 내부공간에 접촉한 치즈 격자는 녹지 않음
• 모눈종이 맨 가장자리에는 치즈가 놓이지 않는 다는 점을 가정 할 때, 치즈가 모두 녹아 없어지는 데 걸리는 정확한 시간 구하기

시간 제한

• 1초

입력

• 모눈 종이의 크기를 나타내는 정수 N, M
  • 5 ≤ N, M ≤ 100
• 그 다음 N개의 줄에 모눈종이 위 격자에 치즈 있는 부분은 1, 없는 부분은 0으로 표시

출력

• 치즈가 모두 녹는데 걸리는 정확한 시간은?

접근법

• map 상태를 아래 4개의 상수변수로 구성했다. ⇒ makeMap
  • 외부공기 EXTERIOR = 0
  • 치즈 CHEEZE = 1
  • 내부공기 INTERIOR = 2
  • 녹을 치즈 WILLMELT= 3 
• 전체 치즈가 0이 될 때까지
  • 녹을 치즈 차기 ⇒ setWillMelt
  • 치즈 녹이기 ⇒ meltCheeze
  • 만약 구멍이 열리면 외부공기 유입하기 ⇒ insertOxygen
  • 위 3가지 로직을 반복했다.

코드

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


public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static Queue<int[]> q = new LinkedList<>();
    static final int EXTERIOR = 0;
    static final int CHEEZE = 1;
    static final int INTERIOR = 2;
    static final int willMelt = 3;
    static int totalCheeze = 0;
    static int answer = 0;

    // 지도 구성하기
    static void makeMap(int row, int col, int state) {
        map[row][col] = state;

        int mrow, mcol;
        for (int dir = 0; dir < 4; dir++) {
            mrow = row + delR[dir];
            mcol = col + delC[dir];

            if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol
                    || visited[mrow][mcol] || map[row][col] != map[mrow][mcol]) continue;

            visited[mrow][mcol] = true;
            makeMap(mrow, mcol, state);
        }
    }

    // 외부공기 유입시키기
    static void insertOxygen(int row, int col) {
        map[row][col] = EXTERIOR;

        int mrow, mcol;
        for (int dir = 0; dir < 4; dir++) {
            mrow = row + delR[dir];
            mcol = col + delC[dir];

            if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol
                    || visited[mrow][mcol] || map[mrow][mcol] == CHEEZE) continue;

            visited[mrow][mcol] = true;
            insertOxygen(mrow, mcol);
        }
    }

    // 녹을 치즈 찾기
    static void setWillMelt(int row, int col) {
        q.offer(new int[]{row, col});
        visited[row][col] = true;

        int crow, ccol, mrow, mcol, cnt;
        while (!q.isEmpty()) {
            crow = q.peek()[0];
            ccol = q.poll()[1];
            cnt = 0;

            for (int dir = 0; dir < 4; dir++) {
                mrow = crow + delR[dir];
                mcol = ccol + delC[dir];

                if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol
                        || visited[mrow][mcol]) continue;

                // 치즈면 담기
                if (map[mrow][mcol] == CHEEZE){
                    q.offer(new int[]{mrow, mcol});
                    visited[mrow][mcol] = true;
                } else if (map[mrow][mcol] == EXTERIOR) {
                    // 외부 공기면 카운트
                    cnt++;
                }
            }

            if (cnt >= 2) {
                // 녹을 예정
                map[crow][ccol] = willMelt;
            }

        }
    }

    // 치즈 녹이기
    static void meltCheeze() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == willMelt){
                    map[i][j] = EXTERIOR;
                    totalCheeze--;
                }
            }
        }
    }

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

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

                if (map[i][j] == CHEEZE) totalCheeze++;
            }
        }

        // 맵구성하기 : 외부공기 = 0, 치즈 = 1, 내부 공기 = 2
        visited = new boolean[N][M];
        boolean meetOxygen = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j]) continue;

                if (map[i][j] == 0) {
                    if (!meetOxygen){
                        makeMap(i, j, EXTERIOR);
                        meetOxygen = true;
                    } else makeMap(i, j, INTERIOR);
                } else if (map[i][j] == CHEEZE) {
                    makeMap(i, j, CHEEZE);
                }
            }
        }

        while (totalCheeze > 0) {
            for (boolean[] v : visited) {
                Arrays.fill(v, false);
            }

            // 시뮬레이션 - 녹을 치즈 찾기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == CHEEZE) {
                        setWillMelt(i, j);
                    }
                }
            }

            // 치즈 녹이기
            meltCheeze();

            for (boolean[] v : visited) {
                Arrays.fill(v, false);
            }

            // 외부 공기 유입하기
            insertOxygen(0,0);

            answer++;
        }

        System.out.println(answer);

    }
}