링크
풀이
⭐⭐⭐ 부분집합과 중복순열이 결합된 문제다.
- 먼저 부분집합(2^n)으로 선택 or not선택 고르고
- 한 가지 경우의 수 완성시 중복순열(4방향^n개)으로 탐색한다.
- 중복순열 호출 하기 전에 선택된 코어의 개수가 현재 max코어개수보다 작다면 호출하지 않고 리턴 (가지치기!)
- 그리고 한 코어에서 한 방향 선택할 때마다 다른 전선 혹은 코어와 교차되는지 확인(checkDir메소드)하고 겹친다면 그 방향은 건너뛴다.
🔥 이 문제를 풀면서 순열, 조합, 부분집합, 중복순열에 대해서 고민하면서 정확한 개념을 정립할 수 있었다. 두 가지 기법을 결합된 문제가 나오니까 헷갈렸다. 저번에 중복순열을 이용해서 풀었던 '감시'문제와 비교해보면서 어떤 점이 다른지, 어떤 조건이 나온다면 어떤 풀이를 사용해야 하는지 알게 됐다.
🔥 코드의 길이가 길어지고 전역변수를 남용할수록 모호해지고 헷갈린다고 느꼈다. 따라서 각 기능별로 메소드를 만들어서 역할을 명확히 하고 지역변수를 생성하고 매개변수를 넘겨주면서 모호성을 줄여야겠다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Solution_1767{
private static int N;
private static boolean[][] map;
private static ArrayList<Point> coreArr;
private static boolean[] vis;
private static int[] dx = { 0, 1, 0, -1 };
private static int[] dy = { 1, 0, -1, 0 };
private static int MaxCoreCnt;
private static int ans;
public static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
map = new boolean[N][N];
coreArr = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
if (Integer.parseInt(st.nextToken()) == 1) {
map[i][j] = true;
//주의!: 가장 자리 코어는 체크는 하지만 coreArr에 넣어서 경우의 수에 포함하지 않는다.
if (i == 0 || i == N - 1 || j == 0 || j == N - 1)
continue;
coreArr.add(new Point(i, j));
}
}
} // 입력완료
vis = new boolean[coreArr.size()]; // subset 배열, 각 코어의 인데스마다 결정했는지 체크
// 코어의 수 최대값 비교 변수
MaxCoreCnt = Integer.MIN_VALUE;
// 전선의 길이의 최소값 비교 변수
ans = Integer.MAX_VALUE;//
subRecur(0, 0);
System.out.println("#" + tc + " " + ans);
}
}
private static void subRecur(int cnt, int selectCnt) { // 부분집합
if (cnt == coreArr.size()) { // 모든 코어에 대하여 O X 결정 완료
// 뽑힌 코어들을 가지고 "중복 순열" 돌리기
// 뽑은 코어들이 개수가 현재 MaxCoreCnt보다 작다면 중복순열 돌릴 필요도 없음(가지치기)
if (selectCnt < MaxCoreCnt)
return;
//중복 순열 안에서 다 탐색하고나서 재귀리턴하면서 원래대로 원상복귀를 시키기 때문에
//초기 map으로 될 것임
//따라서 부분집합 구하는 이 함수에서는 map복귀 로직은 필요 없어보임
ArrayList<Point> tmpCoreList = new ArrayList<>();
for (int i = 0; i < coreArr.size(); i++) {
if (vis[i] == true) {
tmpCoreList.add(coreArr.get(i));
}
}
// 중복 순열 호출
duplicatePerm(tmpCoreList, selectCnt, 0, 0);
return;
}
vis[cnt] = true; // 선택O
subRecur(cnt + 1, selectCnt + 1);
vis[cnt] = false;// 선택X
subRecur(cnt + 1, selectCnt);
}
private static void duplicatePerm(ArrayList<Point> tmpCoreList, int selectCnt, int idx, int LengthSum) {
if (selectCnt == idx) {// 선택된 모든 코어들에 대해서 방향을 정해줬다면
//어느 한 방향이라도 방향이 정해지지 않은 코어가 있다면 기저조건에 도달 못한다.
if(MaxCoreCnt < selectCnt) {
MaxCoreCnt = selectCnt;
ans = LengthSum;
}else if(MaxCoreCnt == selectCnt) {
ans = Math.min(ans, LengthSum);
}
return;
}
// 해당 코어들에 대해서 4방 중복 순열을 돌림
// boolean[][] dfsVisMap = new boolean[N][N];
Point selectCore = tmpCoreList.get(idx);
for (int d = 0; d < 4; d++) {
// 그쪽 방향을 쭉 갔을 때, 갈 수 있는지 체크하고 true리턴하면
// map에 표시
if (checkDir(selectCore, d)) {
//지금의 map 복사해둔다.
boolean[][] copyMap = new boolean[N][N];
for (int i = 0; i < N; i++) {
copyMap[i] = Arrays.copyOf(map[i], N);
}
int nx = selectCore.x+ dx[d];
int ny = selectCore.y + dy[d];
//해당 코어의 해당 방향에서 선택된 전선의 길이를 카운트함
int tmpLengthCnt = 0;
while(inRange(nx, ny)) {
map[nx][ny] = true;
tmpLengthCnt++;
nx += dx[d];
ny += dy[d];
}
//재귀 호출
duplicatePerm(tmpCoreList, selectCnt, idx + 1, LengthSum+tmpLengthCnt);
//map 다시 원상복구
for (int i = 0; i < N; i++) {
map[i] = Arrays.copyOf(copyMap[i], N);
}
}//end of 해당 방향
}//end of 4방 탐색
}//end of duplicatePerm()
private static boolean checkDir(Point selectCore, int d) {
int nx = selectCore.x+ dx[d];
int ny = selectCore.y + dy[d];
while(inRange(nx, ny)) {
if(map[nx][ny] == true) return false;
nx += dx[d];
ny += dy[d];
}
return true;
}
private static boolean inRange(int nx, int ny) {
return nx >= 0 && nx < N && ny >= 0 && ny < N;
}
}
처음부터 모든 경우의 수를 list에 전부 넣고 푼 코드
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Solution_1767 {
private static int N;
private static boolean[][] map;
private static ArrayList<Core> coreDirArr; //방향을 고려한 각각의 코어에 대한 배열
private static int MaxCoreCnt;
private static int ans;
private static boolean[] coreDirCheck;
private static boolean[] coreCheck;
private static int size;
private static int c;
public static class Core{
int x, y, length, numbering, dir; //length: 해당 dir방향의 길이, numbering: 코어에 대한 넘버링
//dir: 4가지 방향 (상 하 좌 우)
public Core(int x, int y, int length, int numbering, int dir) {
this.x = x;
this.y = y;
this.length = length;
this.numbering = numbering;
this.dir = dir;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
map = new boolean[N][N];
int numbering =0;
coreDirArr = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int tmp = Integer.parseInt(st.nextToken());
if(tmp == 1) {
map[i][j] = true; //가장자리는 경우의 수를 탐색하진 않지만 체크는 해야하는 것을 주의하자
if(i == 0 || j == 0 || i == N-1 || j == N-1) continue;
coreDirArr.add(new Core(i, j, i, numbering, 1)); //상
coreDirArr.add(new Core(i, j, N-1-i, numbering, 2)); //하
coreDirArr.add(new Core(i, j, j, numbering, 3)); //좌
coreDirArr.add(new Core(i, j, N-1-j, numbering, 4)); //우
numbering++;
}
}
}
size =coreDirArr.size();
coreDirCheck = new boolean[size]; // 방향을 고려한 코어의 체크 배열
coreCheck = new boolean[numbering+1]; //해당 numbering의 코어 체크 배열
MaxCoreCnt =Integer.MIN_VALUE; //코어의 개수 최대값 비교 변수
ans = Integer.MAX_VALUE;//전선의 길이의 최소값
subset(0);
System.out.println("#" + tc + " " + ans);
}//입력완료
}
public static void subset(int idx) {
if(idx == size) {
int length = 0;
int coreCnt = 0;
for(int i = 0; i < size; i++) {
if(coreDirCheck[i]) {
Core tmpC =coreDirArr.get(i);
length+=tmpC.length;
coreCnt++;
}
}
if(coreCnt > MaxCoreCnt) {
MaxCoreCnt = coreCnt;
ans = length;
}else if(coreCnt == MaxCoreCnt) {
ans = Math.min(ans, length);
}
return;
}
Core c = coreDirArr.get(idx);
//뽑는 경우
if(!coreCheck[c.numbering]) { //해당 넘버의 코어가 선택되지 않았다면
if(check(c.x, c.y, c.dir)) {//해당 코어의 방향이 선택 가능하다면
coreCheck[c.numbering] = true;
coreDirCheck[idx] = true;
boolean[][] tmp = new boolean[N][N];
for(int i =0 ; i < N; i++) {
for(int j = 0; j <N; j++) {
tmp[i][j] = map[i][j];
}
}
switch (c.dir) {
case 1: //상
for(int i = 0; i < c.x; i++) {
map[i][c.y] = true;
}
break;
case 2://하
for(int i = c.x+1; i < N; i++) {
map[i][c.y] = true;
}
break;
case 3://좌
for(int j = 0; j < c.y; j++) {
map[c.x][j] = true;
}
break;
case 4:
for(int j = c.y+1; j < N; j++) {
map[c.x][j] = true;
}
break;
}
subset(idx + 1);
//원상복귀
coreCheck[c.numbering] = false;
coreDirCheck[idx] = false;
for(int i =0 ; i < N; i++) {
for(int j = 0; j <N; j++) {
map[i][j]= tmp[i][j];
}
}
}
}
//안뽑는경우
subset(idx+1);
}
private static boolean check(int x, int y, int dir) {
switch (dir) {
case 1: //상
for(int i = 0; i < x; i++) {
if(map[i][y] == true) return false;
}
return true;
case 2: //하
for(int i = x+1; i < N; i++) {
if (map[i][y] == true) return false;
}
return true;
case 3: //좌
for(int j = 0; j < y; j++) {
if(map[x][j] == true) return false;
}
return true;
case 4: //우
for(int j = y +1; j < N; j++) {
if(map[x][j] == true) return false;
}
return true;
}
return false;
}
}
바른 자세로 코딩합니다 👦🏻💻