[SWEA] 1461. 프로세서 연결하기

[1461. 프로세서 연결하기]

문제

---

dfs 로 하나하나 찾아가는 문제이다. 주어진 수 자체가 크지 않아 무식하게 bfs 해도 될 것 같다.

포인트

---

1. 동서남북 방향을 정할 때는 dx, dy 를 (0, -1), (0, 1), (1, 0), (-1, 0) 을 설정해두고 사용하면 편하다.
2. dfs 로 맵을 사용했으면 다시 복구해주는 과정이 중요하다.

코드

---

import java.util.Scanner;

public class Solution {
	static int[][] core; // 코어들의 인덱스 저장
	static int[][] mat;
	static int cnt; // 총 코어 수
	static int max_core; // 현재까지 코어를 가장 많이 사용한 수
	static int min_edge; // 가장 높은 코어 중 최단거리
	static int N;

	private static int dx[] = {0, 0, -1, 1};
	private static int dy[] = {-1, 1, 0, 0};

	private static void dfs(int idx, int corecnt, int wirecnt) {
		if (idx == cnt) {
			if (max_core < corecnt) {
				max_core = corecnt;
				min_edge = wirecnt;
			} else if (max_core == corecnt) {
				min_edge = Math.min(wirecnt, min_edge);
			}
			return;
		}
		// 인덱스 위치의 코어의 좌표
		int x = core[idx][0];
		int y = core[idx][1];

		// 4방향 탐색
		for (int dir = 0; dir < 4; dir++) {
			int count = 0;
			int nx = x;
			int ny = y;

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

				if (outRange(ny, nx)) break;

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

			int fill_x = x;
			int fill_y = y;

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

			if (count == 0) dfs(idx + 1, corecnt, wirecnt);
			else {
				dfs(idx + 1, corecnt + 1, wirecnt + count);

				//복구
				fill_x = x;
				fill_y = y;
				for (int i = 0; i < count; i++) {
					fill_y += dy[dir];
					fill_x += dx[dir];
					mat[fill_y][fill_x] = 0;
				}
			}
		}
	}

	private static boolean outRange(int ny, int nx) {
		if (ny < 0 || ny >= N || nx < 0 || nx >= N) return true;
		return false;
	}

	public static void main(String args[]) throws Exception {
		try (Scanner sc = new Scanner(System.in)) {
			int T;
			T = sc.nextInt();

			core = new int[12][2];
			mat = new int[13][13];
			for (int test_case = 1; test_case <= T; test_case++) {
				max_core = 0;
				cnt = 0;
				min_edge = 144;
				N = sc.nextInt();
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						mat[i][j] = sc.nextInt();
						if (mat[i][j] == 1 && (i != 0 && j != 0 && i != N - 1 && j != N - 1)) {
							core[cnt][1] = i;
							core[cnt][0] = j;
							cnt++;
						}
					}
				}

				dfs(0, 0, 0);
				System.out.println("#" + test_case + " " + min_edge);

				for (int i = 0; i < 12; i++) {
					core[i][0] = core[i][1] = 0;
				}
			}
		}
	}
}