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

문제 링크

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

SW Expert Academy

 

# 문제 풀이

구현 + DFS

어떤 코어를 어떤 방향으로 연결했는지에 따라서 값이 달라질 수 있기 때문에 dfs로 모든 경우의 수를 탐색해야겠다고 생각했습니다.

1. 멕시노스의 가장자리에 위치한 코어는 이미 전원이 연결된 것으로 간주하기 때문에 제외하고 리스트에 넣습니다.

2. dfs로 탐색을 합니다. 파라미터로 어떤 Core인가, 현재 연결된 Core의 개수, 현재 사용한 Wire의 길이를 넣습니다.

3. 현재 Core의 사방을 탐색합니다. 

- 벽으로 가는 도중에 전선이나 코어를 만나면 연결할 수 없는 방향이므로 break를 합니다. 

- 벽으로 잘 도착했으면 연결이 된 것으로 확인하고 break를 합니다. 

- 연결이 잘 되었는지 확인하는 부분은 count의 숫자입니다. count가 0이면 코어는 연결되지 않은 것이고, 0이 아니면 사용한 전선의 길이를 의미합니다.

- 전선이 연결되었다면 map에 연결된 부분의 위치를 1로 값을 변경합니다.

- 그 다음 연결이 되었다면 원래 연결된 코어 + 1, 원래 사용한 전선의 길이  + count를 해서 다음 코어를 탐색합니다.

- 연결이 안되었다면 원래 값을 바꾸지 않고 다음 코어를 탐색합니다.

- 연결이 된 부분으로 들어갔던 재귀가 끝났다면, map을 원래 값으로 바꿔줘서 다른 탐색에 지장이 가지 않도록합니다.

 

# 문제 코드

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

public class SWEA프로세서 {

	static int t, n, minWire, maxCore;
	static int[][] map;
	static List<Core> coreList;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc < t + 1; tc++) {
			n = Integer.parseInt(br.readLine());
			map = new int[n][n];
			coreList = new ArrayList<Core>();

			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) {
						if (i == 0 || j == 0 || i == n - 1 || j == n - 1)
							continue;
						coreList.add(new Core(j, i));
					}
				}
			}

			minWire = Integer.MAX_VALUE;
			maxCore = Integer.MIN_VALUE;

			dfs(0, 0, 0);

			sb.append("#" + tc + " " + minWire + "\n");
		}
		System.out.println(sb.toString());
	}

	public static void dfs(int index, int wireLength, int coreCount) {
		if (index == coreList.size()) {
			if (coreCount > maxCore) {
				maxCore = coreCount;
				minWire = wireLength;
			} else if (coreCount == maxCore && minWire > wireLength) {
				minWire = wireLength;
			}

			return;
		}

		Core core = coreList.get(index);

		for (int i = 0; i < 4; i++) {
			int count = 0, nx = core.x, ny = core.y;

			while (true) {
				nx += dx[i];
				ny += dy[i];

				if (nx < 0 || ny < 0 || nx >= n || ny >= n)
					break;

				if (map[ny][nx] == 1) {
					count = 0;
					break;
				}

				count++;
			}

			int fill_x = core.x;
			int fill_y = core.y;

			for (int j = 0; j < count; j++) {
				fill_x += dx[i];
				fill_y += dy[i];
				map[fill_y][fill_x] = 1;
			}

			if (count == 0)
				dfs(index + 1, wireLength, coreCount);
			else {
				dfs(index + 1, wireLength + count, coreCount + 1);

				fill_x = core.x;
				fill_y = core.y;

				for (int j = 0; j < count; j++) {
					fill_x += dx[i];
					fill_y += dy[i];
					map[fill_y][fill_x] = 0;
				}

			}

		}

	}

	public static class Core {
		int x, y;

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