[SWEA] Test샘플문제 - (dfs) 1767번 프로세서 연결하기 문제
휴...끝
아직 dfs, bfs관련해 풀수 있는 조금이라도 응용된 문제가 나오면 바로 못푼다
문제를 단순하게 생각해보고, 과정을 고민해보다 다른 사람의 풀이,코드를 보고 (사실 보고도 다 이해는 안갔었다..어느정도 이해해놓고 직접 코드를 안보고 짜보는 과정에서야 비로소 이해가 되었다..)
그 다음부터는 최대한 혼자 풀었다
첨엔 막막하고 그랬는데 풀어보고 나니 그래도 많이 도움이 된 느낌..굿
최대한 많은 core를 연결을 하는데, 같은 core수가 나오는 경우가 여러개라면 그중 최소의 전선길이를 출력하는 문제.
크게 dfs / 방향대로 전선을 놓을 수 있는지 확인하는 함수 / 방향대로 전선을 놓는 함수
이렇게 기능을 나누었다
1. 입력받은 멕시노스의 초기상태에서 1로 표시된, core의 위치(x,y)를 ArrayList로 저장한다.
이때 1이면 다 저장하는게 아니라 가장자리에 위치한 core는 제외하고 저장한다.
나는 힌트를 보고 이렇게 했는데, (안봤음 걍 다 넣었을듯)
그렇게 하는 이유는 이미 가장자리에 위치한 core는 전원 연결이 된 상태므로 굳이 탐색할 필요가 없기 때문이다!
2. dfs를 수행한다. 나는 상우하좌 순으로 탐색되도록 했고, 탐색이 가능한 방향이면 해당 방향으로 전선을 채운다.
3. dfs를 쭉 하다가 마지막 core까지 탐색이 다 됐으면 조건하에 maxCoreCount / minLines를 갱신한다.
4. 만약 상우하좌 모든 방향으로도 다 탐색이 되지 않는경우엔 for문 밖으로 나와 그 밑에있는 dfs를 수행하는데,
이때 코어도 전선도 변화한게 없으므로 depth만 +1해주고 나머지는 그대로 가게 한다.
이런식으로 완전탐색을 실행하여 최대 core수에서의 최소 전선길이를 출력해주면 된다..
시간초과라도 뜰까봐 쫄았는데 다행히 2번째에서 pass가 떴다.
(첫번째는 테스트케이스 돌때마다 초기화해줘야 하는 변수 몇개 초기화 안해줘서 틀렸었음)
주석이 주렁주렁한 풀이코드
package D3;
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class ConnectiongProcessor { //SWEA 샘플문제, 프로세서 연결하기 문제
static int[][] board;
static ArrayList<int[]> coreLocation; //각 코어들의 위치(열,행)를 저장할 list
static int[] dirx = {-1, 0, 1, 0}; //열, 상우하좌 순서
static int[] diry = {0, 1, 0, -1}; //행
static int cores;
static int maxCoreCount;
static int minLines; //최대 core갯수사용시 최소 전선길이
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
N = Integer.parseInt(br.readLine());
board = new int[N][N];
minLines = 0;
maxCoreCount = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
//1(코어 발견하면)먼저 가장자리 위치인지 확인, 아니라면 갈수있는 방향인지 확인하고 4방향 탐색
cores = 0; //코어갯수(가장자리 코어 제외)
coreLocation = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 1 && i != 0 && j != 0 && i != N - 1 && j != N - 1) { //코어가 있는 위치, 가장자리에 있는 경우 아닐때
coreLocation.add(new int[] {i, j}); //int배열 초기화, i,j넣어줌
cores++;
}
}
}
dfs(0, 0, 0);
bw.write( "#" + t + " " + minLines);
bw.newLine();
}
bw.flush();
bw.close();
}
static void dfs(int depth, int cCount, int line) { //dfs수행횟수, 연결된 core갯수, 전선길이
if (depth == cores) { //마지막 코어까지 dfs를 수행했다면
if (cCount > maxCoreCount) { //maxCoreCount보다 연결한 core수가 크다면 core갯수, line길이 갱신
maxCoreCount = cCount;
minLines = line; //전
} else if (cCount == maxCoreCount && line < minLines) { //core수가 같고 전선길이가 더 짧다면 line길이 갱신
minLines = line;
}
return; //이전 dfs호출위치로 돌아간다
}
for (int i = 0; i < 4; i++) { //상우하좌 순서로 탐색 ㄱ
if (isAbleDir(i, coreLocation.get(depth))) { //갈수 있는 방향인지 확인되면
//해당 방향으로 채우기 수행
line = line + fillWithLine(i, coreLocation.get(depth), 2); //기존 line수 + 이번에 채운 line수
dfs(depth + 1, cCount + 1, line);
line -= fillWithLine(i, coreLocation.get(depth), 0); //전선으로 표시된거 다시 0으로 돌려놓고 해당만큼의 전선 수 다시 빼줌
}
}
dfs(depth + 1, cCount, line); //다음 dfs로 넘어는 가지만 core개수, line개수는 변화없음
}
static boolean isAbleDir(int d, int[] idx) { //해당 방향으로 갈수있는지 확인
int tempx = idx[0] + dirx[d]; //해당 core위치의 x좌표 + d
int tempy = idx[1] + diry[d]; //해당 core위치의 y좌표 + d
boolean result = true;
while (tempx >= 0 && tempx < N && tempy >=0 && tempy < N) { //배열범위 내 안에서 반복
if (board[tempx][tempy] != 0) { //전선이나 다른 core(1이나 2를 맞닥뜨릴경우)
result = false;
break;
}
tempx += dirx[d];
tempy += diry[d];
}
return result;
}
static int fillWithLine(int d, int[] idx, int value) { //해당 방향에 value값으로 채움(2:전선, 0:되돌려놓기)
int tempx = idx[0] + dirx[d];
int tempy = idx[1] + diry[d];
int lines = 0;
while (tempx >= 0 && tempx < N && tempy >=0 && tempy < N) {
board[tempx][tempy] = value;
lines++;
tempx += dirx[d];
tempy += diry[d];
}
return lines;
}
}