Life Engineering
[SWEA 1767] 프로세서 연결하기 (Java) 본문
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Solution {
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int T, N;
static int[][] map;
static boolean[][] visited;
static ArrayList<int[]> li;
static int answer;
static int maxCon;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
T=Integer.parseInt(br.readLine());
for (int t=1; t<=T; t++) {
N=Integer.parseInt(br.readLine());
map=new int[N][N];
visited=new boolean[N][N];
li=new ArrayList<>();
maxCon=0;
answer=Integer.MAX_VALUE;
for (int i=0; i<N; i++) {
st=new StringTokenizer(br.readLine());
for (int j=0; j<N; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
if (map[i][j]==1 && i>=1 && i<N-1 && j>=1 && j<N-1) {
li.add(new int[] {i,j});
}
}
}
dfs(0, 0, 0);
if (answer!=Integer.MAX_VALUE)
System.out.println("#"+t+" "+answer);
else
System.out.println("#"+t+" "+0);
}
}
private static void dfs(int cnt,int sum, int con) {
if (cnt==li.size()) {
if (con>maxCon) {
maxCon=con;
answer=sum;
}
else if (con==maxCon) {
answer=Math.min(answer, sum);
}
return;
}
for (int i=0; i<4; i++) {
if (isPromising(cnt, i)) { //겹치지 않는지 체크
int n=mark(cnt, i, true);
dfs(cnt+1, sum+n, con+1);
mark(cnt, i, false);
}
}
dfs(cnt+1, sum, con);
}
private static boolean isPromising(int cnt, int dir) {
int r=li.get(cnt)[0];
int c=li.get(cnt)[1];
while (true) {
r+=dr[dir];
c+=dc[dir];
if (r<0 || c<0 || r>=N || c>=N) break;
if (visited[r][c]) return false;
if (map[r][c]==1) return false;
}
return true;
}
private static int mark(int cnt, int dir, boolean marker) {
int sum=0;
int r=li.get(cnt)[0];
int c=li.get(cnt)[1];
while (true) {
if (r<0 || c<0 || r>=N || c>=N) break;
visited[r][c]=marker;
sum++;
r+=dr[dir];
c+=dc[dir];
}
return sum-1;
}
}
DFS+시뮬레이션 문제.
처음에 가지치기를 시도했다가, 오답이 발생했다.. 잘 생각해보니 (sum>answer) 같은 경우, 만약 지금 sum이 저장되었을 때 연결된 프로세서가 answer 가 저장되었을 때 연결된 프로세서보다 더 크다면 그 가지치기는 유효하지 않으므로 제외해 주었다.
그리고 이 문제의 포인트는
1) 4방향 탐색하며 넣어줄 곳이 유효한지 찾기 + 아예 넣지 않기 (by DFS)
2) 연결된 프로세서 크기가 기존에 저장된 연결되었던 연결된 프로세서의 크기보다 더 크다면, answer이 어떻든 간에 answer을 그 sum으로 변경해 줄것
3) 연결된 프로세서 크기가 기존에 저장된 연결되었던 연결된 프로세서의 크기와 같다면 더 작은 값으로 업데이트
이 3개의 포인트를 캐치하는게 중요했다.. 그리고 가지치기를 함부로 하면 안되었다..
가지치기 했다가 더 연결되었을 경우가 있으므로, 가지치기를 하면 답이 되는 case 를 빼버릴 가능성이 있다.
'Problem Solving' 카테고리의 다른 글
[SWEA 5656] 벽돌 깨기 (Java) (0) | 2022.04.05 |
---|---|
[BOJ 1644] 소수의 연속합 (Java) (0) | 2022.04.04 |
[BOJ 1175] 배달 (Java) (0) | 2022.04.04 |
[BOJ 14442] 벽 부수고 이동하기 2 (Java) (0) | 2022.04.03 |
[BOJ 20057] 마법사 상어와 토네이도 (Java) (0) | 2022.04.01 |