[Java] SW Expert Academy, SW 상시 역량테스트 모의 테스트 1767번 문제 (완전 탐색, DFS, 깊이 우선 탐색)

---문제---

• 1767. [SW Test 샘플문제] 프로세서 연결하기

---코드---

 

이 경우는, 한 node를 지나가면 또 다른 후보가 나오고 그 후보들을 차례로 보고 다음 또 후보가 나오는
bfs(너비 우선 방식)방식 보다는, 각자의 node에서의 가능성을 판단하고 일단 이 경우에서

다음 node로 넘어가는 연쇄적인 방식을 반복하는 dfs의 구현이 더욱 가능성 있다고 판단하였는데,

그 이유는 그렇게 해야 앞에서의 완성형의 (가능한 모든 core를 연결한 경우) 최댓값, 최솟값을 알 수 있고
이를 이용하면 마치 분기한정(Branch & Bound) 처럼 탐색의 갯수를 줄일 수 있었기 때문입니다. (기저사례 1번 참고)

 

import java.util.ArrayList;
import java.util.Scanner;
//import java.io.FileInputStream;
import java.io.FileNotFoundException;

public class Sw1767 {
	static class Location {
		// 코어가 있는 위치를 저장 할 클래스
		int row;
		int column;

		Location(int a, int b) {
			this.row = a;
			this.column = b;
		}

	}

	static int[][] number;
	static int core_cnt, min_len;
	static ArrayList<Location> core; 		// core 위치들의 목록
	static int[] dx = { -1, 1, 0, 0 };		// 좌우상하
	static int[] dy = { 0, 0, -1, 1 };
	static int N;

	public static void dfs(int idx, int cnt, int len) {
		
		// 기저 사례 시작 (Base case)
		if (core.size() - idx < core_cnt - cnt)
			// 1. 남은 core 갯수가 채워야 할 갯수보다 적은 경우
			// 어차피 최대 갯수의 core를 연결하지 못하니까 종료
			return;

		if (idx == core.size()) {
			// 2. 마지막 core 까지 확인이 끝난 경우 (DFS의 마지막 깊이까지 검사한 경우)
			if (cnt > core_cnt) {
				// 2-1. 연결 코어 갯수가 현재까지의 최대 연결 갯수보다 큰 경우
				core_cnt = cnt;
				min_len = len;
			} else if (len < min_len && cnt == core_cnt) {
				// 2-2. 연결 코어가 최대 연결 갯수와 같은데 
				// 연결 길이가 지금까지의 최소 길이 보다 작은 경우
				min_len = len;
			}
			return;
		}
		// 기저 사례 끝
		
		// 현재 단계 검사 시작
		int x = core.get(idx).column;
		int y = core.get(idx).row;
		
		// 1. 좌우상하 순으로 dfs방식으로 검사
		for (int i = 0; i < 4; ++i) {
			int tmp_len = 0;
			boolean check = false;
			int new_x = x;
			int new_y = y;
			
			// 1-1. 현재 core의 라인을 한 방향으로 검사
			while (true) {
				new_x += dx[i];
				new_y += dy[i];
				if (new_x < 0 || new_x > N - 1 || new_y > N - 1 || new_y < 0)
					// 1-1-1. 검사 끝난 경우
					break;
				if (number[new_y][new_x] == 1) {
					// 1-1-2. 한 라인에 다른 선이나 core를 발견한 경우 종료
					check = true;
					break;
				} else {
					// 1-1-3. 선을 놓을 수 있는 길의 경우 임시 길이 추가
					++tmp_len;
				}
			}
			
			// 1-2. 다음 core검사 호출
			if (check) {
				// 1-2-1. 현재 core는 연결하지 못하니까 바로 다음 core검사 시작
				dfs(idx + 1, cnt, len);
			} else {
				// 1-2-2. 현재 core를 i번째 방향으로 선을 연결하고 다음 core검사 시작
				new_x = x;
				new_y = y;
				for (int j = 0; j < tmp_len; ++j) {
					new_x += dx[i];
					new_y += dy[i];
					number[new_y][new_x] = 1;
				}
				dfs(idx + 1, ++cnt, len + tmp_len);
				// 1-2-3. 다시 다른 방향으로도 검사해보기 위해 지도를 원래대로 돌려놓기
				new_x = x;
				new_y = y;
				for (int j = 0; j < tmp_len; ++j) {
					new_x += dx[i];
					new_y += dy[i];
					number[new_y][new_x] = 0;
				}
				--cnt;
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		//System.setIn(new FileInputStream("1767.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		core = new ArrayList<Location>();

		for (int t = 1; t <= T; t++) {
			N = sc.nextInt();
			core_cnt = 0;
			number = new int[N][N];
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					number[i][j] = sc.nextInt();
					if (number[i][j] == 1) {
						if (i == 0 || j == 0 || i == N - 1 || j == N - 1) {
							// 벽에 붙은 core
							++core_cnt;
						} else{
							core.add(new Location(i, j));
						}
					}
				}
			}
			min_len = Integer.MAX_VALUE;
			dfs(0, core_cnt, 0);
			System.out.printf("#%d %d\n", t, min_len);
			core.removeAll(core);
		}

		sc.close();
	}

}

 

몇 시간을 정답을 고민하다가 푼 문제입니다. ㅠㅠ

완전 탐색의 접근 방법도 생각을 했으나 또 다른 효율적 방법이 있지 않을까하는 생각 때문에 넘기고

다른 걸 시도하다 삽질만 여러번 했습니다.

 

계속 다른 방법 찾아보다가 도저히 생각이 안나서 다른 분들은 어떻게 풀었을까 하고 찾아보니

dfs가 많이 나와서 .. 결국 이 방식으로 풀었습니다ㅎㅎ.. (포스팅 해 주신 다른 분들 감사합니다)

새해 목표로 삼성 sw 상시 역량 테스트 A 등급을 따려고 했는데

이런 저의 풀이 속도를 보니 목표를 위해서 많은 노력을 해야겠다는 생각이 들었습니다.

 

이를 통해 문제를 효율적으로 풀 방법이 생각나지 않고, 또 case의 가능 갯수가 적을 때 (N의 범위가 작을 때)

dfs를 쓰는 것이구나 라는 걸 깨닫게 된 것 같습니다.

 

 

---출처---

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy