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

SW Expert Academy 1767 프로세서 연결하기

수업시간에 푼 문제였는데, 그 당시에는 조합, dfs를 막 공부하던 시점이라서 이해가 안되었다.
그냥 강사님이 풀어주신대로만 따라갔다. 그래서 스스로 못푼 문제라 따로 포스팅을 안했다.

오늘 다시 문제를 풀었는데 1시간 20분정도 걸려서 풀 수 있었다.
그런데 깔끔하게 푼건아니고 최적화가 안된 부분도 많았고, 쓸데없이 배열을 여러번 복사했다.
나중에 확인해보니 기존에 강사님이 풀어주신 코드랑 속도차이가 5~6배까지 났다.

풀이 아이디어

배열 끝에 위치한 코어들은 자동으로 전원이 공급되기 때문에, 전선을 이을 필요가 없다.
2차원 배열에 값을 넣으면서 배열 가장자리에 위치한 코어들을 제외하고, 나머지 코어들의 좌표 정보를 배열에 저장했다.
배열의 범위를 관리하기위해 corecount를 증가시키며 배열에 넣어주었다.
-> 강사님은 링크드 리스트로 구현했다.

배열을 복사하고 이제 모든 코어에 대해 순차적으로 조합을 돌리면서 4방향으로 깊이 우선 탐색을 한다.
4방향으로 for문을 사용해서 각 방향마다 전선을 이을수 있는지 여부를 먼저 파악한다.
이을수 있다면 전선이 겹치지 않도록 복사된 배열 좌표에서 이은 전선의 값을 바꾸어준다.
여기서 탐색하는 함수를 다시 호출한다.

블로그에 글을 쓰다보니 실행시간이 오래 걸렸던 이유와, 필요없는 로직들을 발견할 수 있었다.
시간에 쫓겨서 문제를 풀다보니 효율적인 코드보다는 일단 작동이 되는 코드를 작성하느라, 필요없는 부분을 반복하는 로직이 꽤 있었던 것 같다.

이렇게 문제를 다시 보면서 최적화 해보니 처음에 강사님이 풀어주신 코드보다 시간도 적게 걸리고, 메모리도 적게 사용했다.
그리고 스트링 빌더 쓸때는 마지막에 줄바꿈을 넣어 주는거 생각해야한다.

원래코드

package com.algo.swea;

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Solution{
	private static int[][] map;
	private static int N;
	private static int[][] core;
	private static int corecount;
	public static void main(String args[]) throws Exception	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			N= Integer.parseInt(br.readLine());
			map = new int[N][N];
			core =new int[12][2];
			corecount = 0;
			for (int i = 0; i < map.length; i++) {
				String line = br.readLine();
				for (int j = 0, k=0; j < map.length; k+=2,j++) {
					int temp = line.charAt(k)-'0';
					map[i][j]= temp;
					if(temp==1 && i!=0 && i!=N-1 && j!=0 && j!=N-1) {
						core[corecount][0]= i;
						core[corecount++][1]= j;
					}
				}//innermap for
			}//map for
			minLine = Integer.MAX_VALUE;
			maxcore = Integer.MIN_VALUE;
			copymap = new int[N][N];
			connect(0,0);
			System.out.println("#"+testCase+" "+minLine);
		}//testCase
	}
	private static int[] dx = {-1,0,1,0};
	private static int[] dy = {0,-1,0,1};
	private static int[][] copymap;
	private static int minLine;
	private static int maxcore;

	private static void connect(int start, int cnt) {
		if(start==corecount) {
			if(cnt<maxcore) return;
			int count = 0;
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					if(copymap[i][j]==2) {
						count++;
					}
				}
			}
			if(cnt>maxcore) {
				maxcore = cnt;
				minLine = count;
			}else if(cnt==maxcore) {
				minLine = Math.min(count, minLine);
			}

		}		
		for (int k = 0; k < copymap.length; k++) {
			System.arraycopy(map, 0, copymap, 0, N);
		}
		for (int i = start; i < corecount; i++) { //각 코어별로
			int posx =core[i][0];
			int posy =core[i][1];
			//4방향에 대해서 탐색
			for (int j = 0; j < 4; j++) {
				if(!checkLine(posx, posy, j, copymap)) {//갈수 없는 방향이라면
					continue;
				}
				//갈수 있다면 값을 바꿔줘야한다.
				markLine(posx,posy,j, copymap);
				connect(i+1, cnt+1);
				//가지 않는다면 원래대로 고쳐준다.
				celanLine(posx,posy,j,copymap);
			}
			connect(i+1, cnt);
		}

	}
	private static void celanLine(int x, int y, int dir, int[][] map) {
		while(x>0 && x<N-1 && y>0 && y<N-1) {
			x+= dx[dir];
			y+= dy[dir];
			map[x][y]=0;
		}

	}
	private static void markLine(int x, int y, int dir, int[][] map) {
		while(x>0 && x<N-1 && y>0 && y<N-1) {
			x+= dx[dir];
			y+= dy[dir];
			map[x][y]=2;
		}

	}
	//끝까지 갈 수 있으면 true 없으면 false를 리턴
	private static boolean checkLine(int x, int y, int dir, int[][] copymap) {
		while(x>0 && x<N-1 && y>0 && y<N-1) {
			x+= dx[dir];
			y+= dy[dir];
			if(copymap[x][y]!=0) { //maP의 값이 0이 아닌 경우 = 코어 또는 전선이 있는 경우
				return false;
			}
		}
		return true;
	}
}

포스팅 쓰면서 최적화, 수정한 코드

package com.algo.swea;

import java.io.BufferedReader;
import java.io.InputStreamReader;

class SWEA1767ProcessorSolutionMineOptimize{
	private static int[][] map;
	private static int N;
	private static int[][] core;
	private static int corecount;
	public static void main(String args[]) throws Exception	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			N= Integer.parseInt(br.readLine());
			map = new int[N][N];
			core =new int[12][2];
			corecount = 0;
			for (int i = 0; i < map.length; i++) {
				String line = br.readLine();
				for (int j = 0, k=0; j < map.length; k+=2,j++) {
					int temp = line.charAt(k)-'0';
					map[i][j]= temp;
					if(temp==1 && i!=0 && i!=N-1 && j!=0 && j!=N-1) {
						core[corecount][0]= i;
						core[corecount++][1]= j;
					}
				}//innermap for
			}//map for
			minLine = Integer.MAX_VALUE;
			maxcore = Integer.MIN_VALUE;
			copymap = new int[N][N];
			for (int k = 0; k < copymap.length; k++) {
				System.arraycopy(map, 0, copymap, 0, N);
			}
			connect(0,0);
			sb.append("#").append(testCase).append(" ").append(minLine).append("\n");
		}//testCase
		System.out.print(sb);
	}
	private static int[] dx = {-1,0,1,0};
	private static int[] dy = {0,-1,0,1};
	private static int[][] copymap;
	private static int minLine;
	private static int maxcore;

	private static void connect(int start, int cnt) {
		if(start==corecount) {
			if(cnt<maxcore) return;
			int count = 0;
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					if(copymap[i][j]==2) {
						count++;
					}
				}
			}
			if(cnt>maxcore) {
				maxcore = cnt;
				minLine = count;
			}else if(cnt==maxcore) {
				minLine = Math.min(count, minLine);
			}
			return;

		}		
			int posx =core[start][0];
			int posy =core[start][1];
			//4방향에 대해서 탐색
			for (int j = 0; j < 4; j++) {
				if(!checkLine(posx, posy, j, copymap)) {//갈수 없는 방향이라면
					continue;
				}
				//갈수 있다면 값을 바꿔줘야한다.
				markLine(posx,posy,j, copymap);
				connect(start+1, cnt+1);
				//가지 않는다면 원래대로 고쳐준다.
				celanLine(posx,posy,j,copymap);
			}
			connect(start+1, cnt);

	}
	private static void celanLine(int x, int y, int dir, int[][] map) {
		while(x>0 && x<N-1 && y>0 && y<N-1) {
			x+= dx[dir];
			y+= dy[dir];
			map[x][y]=0;
		}

	}
	private static void markLine(int x, int y, int dir, int[][] map) {
		while(x>0 && x<N-1 && y>0 && y<N-1) {
			x+= dx[dir];
			y+= dy[dir];
			map[x][y]=2;
		}

	}
	//끝까지 갈 수 있으면 true 없으면 false를 리턴
	private static boolean checkLine(int x, int y, int dir, int[][] copymap) {
		while(x>0 && x<N-1 && y>0 && y<N-1) {
			x+= dx[dir];
			y+= dy[dir];
			if(copymap[x][y]!=0) { //maP의 값이 0이 아닌 경우 = 코어 또는 전선이 있는 경우
				return false;
			}
		}
		return true;
	}
}