이번 주에는 저번 주에 이어서 백트래킹 / 브루트포스 알고리즘 문제를 풀었습니다.
📌 계란으로 계란치기
계란으로 계란치기 문제는 각 계란에는 내구도와 무게가 정해져 있습니다. 계란으로 계란을 치게 되면 각 계란의 내구도는 상대 계란의 무게만큼 깎이게 됩니다. 그리고 내구도가 0 이하가 되는 순간 계란은 깨지게 됩니다.
예를 들어 계란 1의 내구도가 7, 무게가 5이고 계란 2의 내구도가 3, 무게가 4라고 해보겠습니다. 계란 1으로 계란 2를 치게 되면 계란 1의 내구도는 4만큼 감소해 3이 되고 계란 2의 내구도는 5만큼 감소해 -2가 됩니다. 충돌 결과 계란 1은 아직 깨지지 않았고 계란 2는 깨졌습니다.
조금 더 상세하게 계른을 치는 과정은 다음과 같습니다.
-
가장 왼쪽의 계란을 든다.
-
손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
-
가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
일렬로 놓인 계란들의 내구도와 무게가 차례대로 주어졌을 때 위의 과정을 통해 최대 몇 개의 계란을 깰 수 있는지 출력하는 문제입니다.
💡 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
private static int n;
private static int[][] arr;
private static int answer = Integer.MIN_VALUE;
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());
// 계란의 내구도와 무게 저장 배열
arr = new int[n][2];
// 계란의 내구도와 무게 입력
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
solve(0, 0);
bw.write(answer+"");
bw.flush();
bw.close();
br.close();
}
public static void solve(int cur, int count){
// 마지막 계란까지 다다랐다면
if(cur == n){
answer = Math.max(answer, count);
return;
}
// 손에 들고 있는 계란이 깨졌거나 계란이 모두 깨졌으면
if(arr[cur][0]<=0 || count==n-1){
solve(cur+1, count);
return;
}
int temp = count;
for(int target=0; target<n; target++){
// 손에 들고있는 계란과 깨뜨릴 계란이 달라야함. 그리고 내구도는 0보다 커야함
if(cur!=target && arr[target][0]>0) {
// 계란 치기
arr[target][0] -= arr[cur][1];
arr[cur][0] -= arr[target][1];
// 손에 들고 있는 계란이 깨졌다면
if(arr[cur][0]<=0) count++;
// 타켓이 된 계란이 깨졌다면
if(arr[target][0]<=0) count++;
solve(cur+1, count);
// 다른 경우의 수를 찾기 위해 계란 복구
arr[target][0] += arr[cur][1];
arr[cur][0] += arr[target][1];
count = temp;
}
}
}
}-
solve()메서드에는손에 들고 있는 계란(cur)과깨뜨린 개수(count)를 매개변수로 받습니다. -
sovle()메서드 안에는for문을 통해 계란을 하나 씩 체크합니다. -
손에 들고 있는 계란(cur)과타켓이 된 계란(target)이 서로 달라야 하며, 타켓이 된 계란의 내구도는 0보다 커야 과정을 진행할 수 있습니다. -
그리고 계란을 쳐서 서로의 내구도를 깎습니다.
-
만약에
손에 들고 있는 계란(cur)또는타켓이 된 계란(target)이 깨졌다면count를 하나 증가시킵니다. -
그리고 다음 계란으로 옮긴 후 재귀 호출합니다.
-
맨 마지막 계란까지 다다랐으면 최댓값 갱신을
return하고, 손에 들고 있는 계란이 깨졌거나 계란이 모두 깨졌으면 과정을 진행 할 수 없으므로 재귀 호출합니다. -
다른 경우의 수를 찾기 위해 깎인 내구도를 복구시킵니다.
📌 소문난 칠공주
소문난 칠공주는 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치된 상태입니다.
여기에 이다솜파와 임도연파, 두 그룹으로 나뉘어져 있으며, 이다솜파가 임도연파에 위협을 받아 이다솜파는 소문난 칠공주를 결성하기로 했습니다.
소문난 칠공주는 다음과 같은 규칙을 만족해야 합니다.
-
이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
-
강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
-
화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
-
그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.
여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 문제입니다.
💡 예제 입력
YYYYY
SYSYS
YYYYY
YSYYS
YYYYY💡 예제 출력
2💡 예제에 대한 힌트
가능한 방법은 아래와 같습니다.
.... .....
SYSYS SYSYS
....Y .Y...
....S .S...
..... .....💡 코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
private static char[][] arr = new char[5][5];
private static int[] combX = new int[25];
private static int[] combY = new int[25];
private static int dx[] = {-1,1,0,0};
private static int dy[] = {0,0,-1,1};
private static int answer = 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));
for(int i=0; i<5; i++){
arr[i] = br.readLine().toCharArray();
}
// 좌표 계산
for(int i=0; i<25; i++){
combX[i] = i % 5;
combY[i] = i / 5;
}
combination(new int[7], 0,0,7);
bw.write(answer+"");
bw.flush();
bw.close();
br.close();
}
public static void combination(int[] comb, int idx, int depth, int left) {
if(left == 0) {
bfs(comb);
return;
}
if(depth == 25) return;
comb[idx] = depth;
combination(comb, idx+1, depth+1, left-1);
combination(comb, idx, depth+1, left);
}
public static void bfs(int[] comb){
Queue<Integer> q = new ArrayDeque<>();
q.add(comb[0]);
boolean[] visited = new boolean[7];
visited[0] = true;
int cnt=1, sCnt=0;
while (!q.isEmpty()){
int cur = q.poll();
// 이다솜파이면
if (arr[combY[cur]][combX[cur]] == 'S') sCnt++;
for(int i=0; i<4; i++){
for(int next=1; next<7; next++){
if(!visited[next] &&
combX[cur]+dx[i] == combX[comb[next]] &&
combY[cur]+dy[i] == combY[comb[next]]) {
visited[next] = true;
q.add(comb[next]);
cnt++;
}
}
}
}
// 7개 모두 연결되어있다면
if(cnt == 7) {
if(sCnt >=4) {
answer++;
}
}
}
} // 좌표 계산
for(int i=0; i<25; i++){
combX[i] = i % 5;
combY[i] = i / 5;
}-
25명의 여학생들을 2차원 배열로 입력받게 되는데, 이를 1차원 배열 인덱스로 표현하면
0 ~ 24로 표현할 수 있습니다. -
0 ~ 24를 이용하여 2차원 배열로 입력받은 각 여학생들의 위치를X 좌표,Y 좌표로 표현하여 미리 저장하기 위함입니다. -
예를 들어, 위의 예제에서 4번째에 위치한
Y를 표현하면,combX[3] = 3,combY[3] = 0로0,3에 위치함을 표현할 수 있습니다.
combination()
- 25명의 여학생들 중에서 7명의 여학생들을 뽑는 메서드
- 7명의 여학생들은
comb[]에 저장 - 7명의 여학생들을 다 뽑았다면
bfs()메서드를 호출
bfs()
- 7명의 여학생들이 서로 인접해 있는지 확인하는 메서드
- 이다솜파면
sCnt를 하나씩 증가 - 현재 위치에서 뽑은 여학생들이 위치와 서로 인접해 있는지 확인하여 인접하면 과정 진행
- 7명의 여학생들의 위치를 확인했고 이다솜파가 4명 이상이면
answer를 하나 증가
