[SWEA 1767] 프로세서 연결하기 (Java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 

SW Expert Academy

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 를 빼버릴 가능성이 있다.