1767. 프로세서 연결하기

링크

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

SW Expert Academy

 

분류

그래프 탐색

완전탐색

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

각 프로세서가 선택할 수 있는 선택지는 네 방향 + 연결 안하기로, 총 다섯가지이다.

즉 5^12가지의 선택지가 있는 셈인데, 그럼에도 불구하고 완전탐색을 선택한 이유는

두 프로세서간의 위치 간섭으로 인해 5^12가지 중에 선택할 수 없는 선택지가 굉장히 많기 때문이다.

이러한 선택지를 제외하게 되면 완전탐색으로 충분히 짧은 시간 안에 해결 가능하다.

 

시행착오

없음

 

코드

import java.util.*;
import java.io.*;

class Solution{
	static int N, cpu_cnt, maxConnected, minWire;
	static CPU[] cpus;
	static int[][] map; // 0 empty / 1 CPU / 2 wire

	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			N = Integer.parseInt(br.readLine());
			cpus = new CPU[12];
			map = new int[N][N];
			cpu_cnt = 0;

			for (int i = 0; i < N; i++){
				String[] arr = br.readLine().split(" ");
				for (int j = 0; j < N; j++){
					map[i][j] = arr[j].equals("0") ? 0 : 1;
					
					if (map[i][j] == 1 && i != 0 && i != N - 1 && j != 0 && j != N - 1) {
						cpus[cpu_cnt++] = new CPU(i, j);
					}
				}
			}

			maxConnected = Integer.MIN_VALUE;
			minWire = Integer.MAX_VALUE;

			for (int i = 0; i < 5; i++) solve(0, i, 0, 0);

			System.out.println("#" + tc + " " + minWire);
		}
	}

	public static void solve(int cpu_idx, int dir, int wire, int connected){
		if (cpu_idx == cpu_cnt){
			if (connected > maxConnected){
				maxConnected = connected;
				minWire = wire;
			}else if (connected == maxConnected && minWire > wire){
				minWire = wire;
			}

			return;
		}

		if (dir == 4){
			for (int i = 0; i < 5; i++) solve(cpu_idx + 1, i, wire, connected);
			return;
		}

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

		int x = cpus[cpu_idx].x, y = cpus[cpu_idx].y;

		while (true){
			x += dx[dir];
			y += dy[dir];

			if (x < 0 || y < 0 || x >= N  || y >= N){
				for (int i = 0; i < 5; i++) solve(cpu_idx + 1, i, wire, connected + 1);
				break;
			}
			if (map[x][y] != 0) break;

			map[x][y] = 2;
			wire++;
		}

		while (true){
			x -= dx[dir];
			y -= dy[dir];

			if (x < 0 || y < 0 || x >= N  || y >= N) break;
			if (map[x][y] != 2) break;

			map[x][y] = 0;
			wire--;
		}
	}

	static class CPU{
		int x, y;

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