📙 Algorithm Solving/Java
📙[Algo] 24.02.21 알고리즘
혜덕hyeduck
2024. 2. 22. 13:29
알고리즘 문제) BOJ 15683. 감시
문제 요약
- N*M 사무실에 K개의 CCTV가 설치
- CCTV 종류는 5가지
- 1번 : 한 방향
- 2번 : 두 방향, 서로 정 반대를 바라봄
- 3번 : 두 방향, 직각 방향일 것
- 4번 : 3방향
- 5번 : 4방향
- CCTV 종류는 5가지
- 감시하는 방향에 있는 칸 전체 감시 가능
- 벽은 통과 X ⇒ 6
- CCTV 방향을 적절히 정해서, 사각 지대의 최소 크기 구하기
시간 제한
- 1초
입력
- 사무실 세로 크기 N, 가로 크기 M
- 1≤N,M≤8
- 사무실 정보
- 0 : 빈칸
- 6 : 벽
- 1~5 : cctv
- cctv는 최대 8개
출력
- 사각 지대 최소 크기 출력
접근법
- 완전 탐색으로 생각하기
- 각 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 방향
- CCTV 클래스
- 백트랙킹
- 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. 매직 스타
문제 요약
- 매직 스타
- 숫자 4개로 이루어진 줄의 숫자를 모두 합하면 26
- 숫자 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)
문제 요약
- 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)
문제 요약
- 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)
문제 요약
- 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. 모든 순열
문제 요약
- 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();
}
}