[SW Expert Academy 1767]프로세서 연결하기(java)

문제보러가기

SW Expert Academy

이문제는 시뮬레이션 문제라고한다. 나는 DFS로 풀었다!

물론 간단하게 푼건 아니고 안되는 테스트 케이스가 있어서 애를 먹었으며, 처음에는 DFS를 쓰면 되겠다 뿐 어떻게 구현하지 생각이 나지않아 다른분들이 푼 순서들을 보며 풀었다.

 

 

 

 

 

고려사항

 

코어를 최대로 연결하는게 목표이지만 같을경우 길이가 짧은걸 반환해야한다.여기서 각각의 코어마다 DFS를 진행할때 코어숫자와 최소 길이를 넘겨줘야한다는걸 알아야한다!

 

시간초과가 났던부분은 코어가 벽에 붙어있을경우 무조건 연결시키면 되므로 core 개수를 +1해버리고 넘어가면 해결이 되는 부분이었다! 

 

마지막 테스트케이스가 fail이 떠서 뭐지 싶었는데 core를 선택을 안할경우도 있다는것을 뺀 코드였기 때문에 이부분을 고쳐주어서 통과를 하였다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Solution{
	// static boolean visited[][];
	static int g[][];
	static int n;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static ArrayList<Core> ar;
	static int maxCore = Integer.MIN_VALUE;
	static int minLine = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int testCase = Integer.parseInt(br.readLine().trim());
        
		for (int i = 0; i < testCase; i++) {
			n = Integer.parseInt(br.readLine().trim());
			g = new int[n][n];
            ar = new ArrayList<Core>();
			String[] str;
			for (int j = 0; j < n; j++) {
				str = br.readLine().split(" ");
				for (int k = 0; k < n; k++) {
					g[j][k] = Integer.parseInt(str[k]);
					if (g[j][k] == 1) {
						ar.add(new Core(j, k));
					}
				}
			}
            
			dfs(0, 0, 0);
			System.out.println("#" + (i + 1) + " " + minLine);
            //전역변수를 사용하므로 테스트 케이스마다 초기화해주기!
			ar.clear();
			maxCore = Integer.MIN_VALUE;
			minLine = Integer.MAX_VALUE;
	

		}

	}

//인자로 코어리스트의 index와 선택된 코어의 개수, 연결선의 길이를 넘겨준다
	public static void dfs(int idx, int coreCnt, int lineLen) {

		if (idx == ar.size()) {
			if (coreCnt > maxCore) {
				maxCore = coreCnt;
				minLine = lineLen;

			} else if (coreCnt == maxCore) {
				if (minLine > lineLen) {
					minLine = lineLen;
				}
			}
			
			return;
		}
		Core c = ar.get(idx);

//남북동서 방향으로 탐색
		for (int i = 0; i < 4; i++) {
        
//벽에 붙어있는 코어이면 탐색하지 않고 코어의 개수를 늘림
			if (c.x == 0 || c.x == n - 1 || c.y == 0 || c.y == n - 1) {
				dfs(idx + 1, coreCnt + 1, lineLen);
				break;

			}
            //그방향으로 연결이 가능한지 체크
			int check = checkLine(i, c);
			int sx = c.x;
			int sy = c.y;
            //연결이 가능하다면 길이와 코어개수와 라인길이를 갱신해서 계속 탐색
			if (check != -1) {
				dfs(idx + 1, coreCnt + 1, lineLen + check);
             	//후에 다시 사용되므로 라인으로 체크되는 배열을 초기화
				for (int j = 0; j < check; j++) {
					sx += dx[i];
					sy += dy[i];
					g[sx][sy] = 0;

				}
			}

		}
        //코어를 선택하지않고 넘어가는 경우도 탐색
		dfs(idx + 1, coreCnt, lineLen);
	}

//연결이 가능한지 체크해주는함수
	public static int checkLine(int i, Core c) {
		int line = 0;
		int sx = c.x + dx[i];
		int sy = c.y + dy[i];
		boolean check = false;
		while (true) {
			line++;
				if ((sx == 0 || sx == n - 1 || sy == 0 || sy == n - 1) && g[sx][sy] == 0) {
					check = true;
					break;
				}
				if (g[sx][sy] != 0) {
					check = false;
					break;
				}
			sx += dx[i];
			sy += dy[i];

		}
		sx = c.x;
		sy = c.y;
        //연결이 가능하다면 라인을 2로 표시해주면서 그어줌
		if (check) {
			for (int idx = 0; idx < line; idx++) {
				sx += dx[i];
				sy += dy[i];
				g[sx][sy] = 2;

			}
			return line;
		}
		return -1;
	}

}

class Core {
	int x;
	int y;

	Core(int x, int y) {
		this.x = x;
		this.y = y;
	}

}

 

 

 

DFS/BFS는 많이 사용되므로 활용문제를 많이 풀어서 익혀야겠다! 어떤식으로 사용해야 효율적인지가 중요한 문제인것 같다. 이런문제는 시간초과 확인하면서 풀것!!