📙[Algo] 24.02.21 알고리즘

알고리즘 문제) BOJ 15683. 감시

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

문제 요약

• N*M 사무실에 K개의 CCTV가 설치
  • CCTV 종류는 5가지
    • 1번 : 한 방향
    • 2번 : 두 방향, 서로 정 반대를 바라봄
    • 3번 : 두 방향, 직각 방향일 것
    • 4번 : 3방향
    • 5번 : 4방향
• 감시하는 방향에 있는 칸 전체 감시 가능
• 벽은 통과 X ⇒ 6
• CCTV 방향을 적절히 정해서, 사각 지대의 최소 크기 구하기

시간 제한

• 1초

입력

• 사무실 세로 크기 N, 가로 크기 M
  • 1≤N,M≤8
• 사무실 정보
  • 0 : 빈칸
  • 6 : 벽
  • 1~5 : cctv
  • cctv는 최대 8개

출력

• 사각 지대 최소 크기 출력

접근법

1. 완전 탐색으로 생각하기
   • 각 CCTV 마다 바라보는 방향의 종류 수가 다르다
   • 1번 : 4개
   • 2번 : 2개
   • 3번 : 4개
   • 4번 : 4개
   • 5번 : 1개
   • 만약 cctv가 1번, 1번, 2번, 2번 이렇게 주어진다면 나올 수 있는 모든 경우의 수는 442*2 = 64가지임
   • cctv 개수가 S개라면
   • S 크기를 갖고 CCTV 타입의 selected 배열을 하나 만든다.
     • CCTV 클래스
       • no : CCTV 번호
       • dir : CCTV 방향
2. 백트랙킹
   • for문의 범위는 1~4로 설정
   • selected[i].no에 따라 적절하게 dir값을 넣는다.
   • cur == S일 때, 설정한 CCTV 방향에 따라 map을 갱신한다. (0→-1)
   • 갱신하면서 0의 개수 감소 시키기(초반에 map을 입력 받을 때 0개수 카운팅)
   • 0의 개수 최솟값인 경우로 정답 갱신하기

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M; // map 크기
    static int S; // CCTV 개수
    static int zero; // 0개수
    static int[][] map; // 사무실 정보
    static int[][] copyMap; // 사무실 복사본
    static ArrayList<CCTV> selected; // CCTV별로 방향을 선택한 경우
    static int[] delR = {-1, 1, 0 ,0}; // 상하좌우
    static int[] delC = {0, 0, -1, 1}; // 상하좌우
    static int[][][] cctvs = {{},
            {{0}, {1}, {2}, {3}},
            {{0, 1}, {2, 3}},
            {{0, 3}, {0, 2}, {1, 3}, {1, 2}},
            {{0, 2, 3}, {1, 2, 3}, {0, 1, 2}, {0, 1, 3}},
            {{0, 1, 2, 3}}};
    static int answer = Integer.MAX_VALUE; // 사각지대 최솟값

    static class CCTV {
        int no; // CCTV 번호
        int dir; // CCTV 방향
        int row; // cctv 좌표 row값
        int col; // cctv 좌표 col값

        CCTV(int no, int dir, int row, int col) {
            this.no = no;
            this.dir = dir;
            this.row = row;
            this.col = col;
        }
    }

    static void copyMap() {
        zero = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copyMap[i][j] = map[i][j];
                if(copyMap[i][j] == 0) zero++;
            }
        }
    }

    static void updateMap(int no, int dir, int row, int col) {
        for (int k = 0; k < cctvs[no][dir].length; k++) {
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[]{row, col});

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

                mrow = crow + delR[cctvs[no][dir][k]];
                mcol = ccol + delC[cctvs[no][dir][k]];

                if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol || copyMap[mrow][mcol] == 6) break;

                if (copyMap[mrow][mcol] == 0) {
                    zero--;
                    copyMap[mrow][mcol] = -1;
                    q.offer(new int[]{mrow, mcol});
                } else {
                    q.offer(new int[]{mrow, mcol});
                }
            }
        }
    }

    static  void recur(int cur) {
        if (cur == S) {
            copyMap();
            for (int i = 0; i < S; i++) {
                updateMap(selected.get(i).no, selected.get(i).dir, selected.get(i).row, selected.get(i).col);
            }
            answer = Math.min(zero, answer);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (i >= 2 && selected.get(cur).no == 2) {
                selected.get(cur).dir = i % 2;
            } else if (i >= 1 && selected.get(cur).no == 5) {
                selected.get(cur).dir = i % 1;
            } else {
                selected.get(cur).dir = i;
            }
            recur(cur + 1);
        }
    }

    static void printMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(copyMap[i][j]+" ");
            }
            System.out.println();
        }
    }

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

        map = new int[N][M];
        copyMap = new int[N][M];
        selected = new ArrayList<>();
        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] == 1) selected.add(new CCTV(1, -1, i, j));
                else if(map[i][j] == 2) selected.add(new CCTV(2, -1, i, j));
                else if(map[i][j] == 3) selected.add(new CCTV(3, -1, i, j));
                else if(map[i][j] == 4) selected.add(new CCTV(4, -1, i, j));
                else if(map[i][j] == 5) selected.add(new CCTV(5, -1, i, j));
            }
        }
        S = selected.size();
        recur(0);

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

 

알고리즘 문제) BOJ 3967. 매직 스타

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

문제 요약

• 매직 스타
  • 숫자 4개로 이루어진 줄의 숫자를 모두 합하면 26
    

    

• 일부만 채워진 매직 스타가 주어졌을 때, 수를 전부 채워 매직스타 만들기

시간 제한

• 1초

입력

• 매직스타 모양이 주어짐
  • 수가 채워져 있지 않은 곳은 x
  • ‘A’ ~ ‘L’까지 채워져 있음
    • i번째 알파벤은 숫자 i를 의미
  • 매직스타 모양이 아닌곳은 ‘.’

출력

• 매직스타를 만들 수 있는 방법 중 사전 순으로 가장 앞서는 방법 출력
  • 모든 줄을 순서대로 붙여서 하나의 문자열로 만든 뒤, 사전 순으로 비교

접근법

• 별모양 줄의 합계를 어떻게 구해야하지?
             (0,4)
  (1,1)(1,3)(1,5)(1,7)
       (2,2)      (2,6)
  (3,1)(3,3)(3,5)(3,7)
              (4,4)

0	1	2	3	4	5	6	7	8	9	10	11
0,4	1,1	1,3	1,5	1,7	2,2	2,6	3,1	3,3	3,5	3,7	4,4

• 합계
  • arr[1]+arr[2]+arr[3]+arr[4]
  • arr[7]+arr[8]+arr[9]+arr[10]
  • arr[1]+arr[5]+arr[8]+arr[11]
  • arr[4]+arr[6]+arr[9]+arr[11]
  • arr[0]+arr[2]+arr[5]+arr[7]
  • arr[0]+arr[3]+arr[6]+arr[10]
• 사전순으로 가장 앞서는 것을 출력하는 것이므로, A부터 하나씩 입력하다가 매직스타가 완성되는 순간 정답 출력하고 종료

코드

import java.io.*;

public class Main {
    static char[][] map;
    static boolean[] visited;
    static char[] star;
    static char[] chars = {0, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'};
    static int[][] sumIdx = {{1, 2, 3, 4}, {7, 8, 9, 10}, {1, 5, 8, 11}
            , {4, 6, 9, 11}, {0, 2, 5, 7}, {0, 3, 6, 10}};
    static boolean isEnd;
    static StringBuilder sb = new StringBuilder();

    static boolean check() {
        int sum;
        for (int i = 0; i < 6; i++) {
            sum = 0;
            for (int j = 0; j < 4; j++) {
                sum += star[sumIdx[i][j]] - 64;
            }

            if(sum != 26) return false;
        }
        return true;
    }

    static void recur(int cur) {

        if(isEnd) return;

        if (cur == 12) {

            if (check()) {
                for (int i = 0, k = 0; i < 5; i++) {
                    for (int j = 0; j < 9; j++) {
                        if (map[i][j] != '.') {
                            map[i][j] = star[k++];
                        }
                        sb.append(map[i][j]);
                    }
                    sb.append("\\n");
                }
                isEnd =  true;
            }

            return;
        }

        if (cur < 12 && star[cur] != 'x') {
            recur(cur + 1);
        } else {
            for (int i = 1; i <= 12; i++) {
                if(visited[i]) continue;
                visited[i] = true;
                star[cur] = chars[i];
                recur(cur + 1);
                visited[i] = false;
                star[cur] = 'x';
            }
        }

    }

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

        map = new char[5][9];
        visited = new boolean[13];
        star = new char[12];
        String str;
        for (int i = 0, k = 0; i < 5; i++) {
            str = br.readLine();
            for (int j = 0; j < 9; j++) {
                map[i][j] = str.charAt(j);
                if (0 <= map[i][j] - 'A' && map[i][j] - 'A' < 12 || map[i][j] == 'x') {
                    if (map[i][j] != 'x') {
                        visited[map[i][j] - 'A' + 1] = true;
                    }
                    star[k] = map[i][j];
                    k++;
                }
            }
        }

        recur(0);

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

 

알고리즘 문제) BOJ 15657. N과 M (9)

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

문제 요약

• N개의 자연수 중 M개를 고른 수열
• 같은 수 중복 가능
• 오름차순일것!!

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

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

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static boolean[] visited;
    static Set<String> set = new LinkedHashSet<>();
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur) {
        if (cur == M) {
            sb.setLength(0);
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            set.add(String.valueOf(sb));
            return;
        }

        for (int i = 0; i < N; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            answer[cur] = nums[i];
            recur(cur + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];
        visited = new boolean[N];

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

        Arrays.sort(nums);
        recur(0);

        String[] ans = set.toArray(new String[set.size()]);
        for (String e : ans) {
            System.out.println(e);
        }

        br.close();
    }
}

 

알고리즘 문제) BOJ 15664. N과 M (10)

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

문제 요약

• N개의 자연수 중 M개를 고른 수열
• 비내림차순일것
• 이때 주어지는 수들은 중복도 가능하다.

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

접근법

1 7 9 9

arr : 1 7

arr : 1 9

코드

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

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static Set<String> set = new LinkedHashSet<>();
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur, int start) {
        if (cur == M) {
            sb.setLength(0);
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            set.add(String.valueOf(sb));
            return;
        }

        for (int i = start; i < N; i++) {
            answer[cur] = nums[i];
            recur(cur + 1, i + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];

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

        Arrays.sort(nums);
        recur(0, 0);

        String[] ans = set.toArray(new String[set.size()]);
        for (String e : ans) {
            System.out.println(e);
        }

        br.close();
    }
}

 

알고리즘 문제) BOJ 15666. N과 M (12)

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

문제 요약

• N개의 자연수 중 M개를 고른 수열
• 같은 수 여러번 골라도 됨
• 비내림차순일것

시간 제한

• 1초

입력

• 자연수 N과 M
  • 1≤M≤N≤8
• N개의 수가 주어진다.
  • 수는 10000이하 자연수

출력

• 중복되는 수열은 하나만 출력, 각 수열은 공백으로 구분
• 수열은 사전 순으로 증가해서 출력

코드

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

public class Main {
    static int N, M;
    static int[] nums;
    static int[] answer;
    static Set<String> set = new LinkedHashSet<>();
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur, int start) {
        if (cur == M) {
            sb.setLength(0);
            for (int i = 0; i < M; i++) {
                sb.append(answer[i] + " ");
            }
            set.add(String.valueOf(sb));
            return;
        }

        for (int i = start; i < N; i++) {
            answer[cur] = nums[i];
            recur(cur + 1, i);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new int[N];
        answer = new int[M];

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

        Arrays.sort(nums);
        recur(0, 0);

        String[] ans = set.toArray(new String[set.size()]);
        for (String e : ans) {
            System.out.println(e);
        }

        br.close();
    }
}

 

알고리즘 문제) BOJ 10974. 모든 순열

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

문제 요약

• N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성

시간 제한

• 1초

입력

• N
  • 1≤N≤8

출력

• 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력

접근법

• NPN 구하는 문제

코드

import java.io.*;

public class Main {
    static int N;
    static boolean[] visited;
    static int[] selected;
    static StringBuilder sb = new StringBuilder();

    public static void recur(int cur) {
        if (cur == N) {
            for (int i = 0; i < N; i++) {
                sb.append(selected[i]+" ");
            }
            sb.append("\\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            selected[cur] = i;
            recur(cur + 1);
            visited[i] = false;
        }
    }

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

        visited = new boolean[N + 1];
        selected = new int[N];
        recur(0);

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