easy blog

		
        String path = "C:\\Users\\Lee\\eclipse-workspace\\TestApplication\\output.txt";
        
        File file = new File(path);
		PrintStream ps = new PrintStream(new FileOutputStream(file));
        
		System.setOut(ps);

출처 : https://nabiro.tistory.com/252

전략

1. 약품처리 K를 사용하는 경우의 수를 중복순열을 사용하여 3가지로 정의함.

(-1 : 아무것도 하지 않음)

( 0 : A 약품)

( 1 : B 약품)

2. check 함수를 어떤식으로 구현할까 고민했지만, 탐색을 위한 특별한 전략이 없다고 판단 BF로 진행.

문제 조건을 살펴보면, worst cast의 실행횟수는

3^13 * D*W = 3   ^   13   ×   13   ×   20 = 414,523,980

정도이며 실행시간이 5초 이내임을 감안하면 충분하다 판단함.

3. check 구현시, map을 직접 수정하면 원래대로 되돌리는 것이 번거롭기 때문에 dummy를 생성하여 사용후 버림.

완성 후 다음 사이트와 비교하여, 구현상의 차이점 정도를 살펴보면 좋을듯 싶다.

https://velog.io/@hyeon930/SWEA-2112-%EB%B3%B4%ED%98%B8-%ED%95%84%EB%A6%84-Java

import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;


class Solution {

	static int D, W, K;
	static int[][] skin, dummy;
	private static boolean DBG = false;

	static int min;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {

			st = new StringTokenizer(br.readLine());
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			skin = new int[D][W];
			dummy = new int[D][W];
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					skin[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			// index, cnt
			// 중복 순열
			min=Integer.MAX_VALUE;
			go(0, 0, new int[D]);

			System.out.println("#" + test_case + " " +min);

		}

		System.out.println(sb);

	}

	private static void go(int level, int cnt, int[] perm) {

		if (level == D) {
			if (cnt > K) {
				return;
			}
			StringBuilder sb = new StringBuilder();

			if (DBG) {
				sb.append("perm : \n");
				for (int v : perm)
					sb.append(v).append(' ');
				// System.out.println(sb);
				sb.append('\n');
			}
			// i, perm[i] => map's row , value
			int ii = 0;
			for (int[] ar : skin)
				dummy[ii++] = Arrays.copyOf(ar, ar.length);

			for (int i = 0; i < perm.length; i++) {
				int value = perm[i];
				if (value == -1)
					continue;
				Arrays.fill(dummy[i], value);
			}

			if (DBG) {
				sb.append("dummy : \n");
				for (int[] ar : dummy) {
					for (int v : ar) {

						sb.append(v).append(' ');
					}
					sb.append('\n');
				}
				System.out.println(sb);
			}

			if (check() == true) {
				//System.out.println("pass!");
				min = Math.min(min, cnt);
			} else {
				//System.out.println("NG!");
			}
			
			return;
		}
		// 중복 순열
		for (int i = -1; i < 2; i++) {
			perm[level] = i;
			cnt = (i == -1) ? cnt : cnt + 1;
			go(level + 1, cnt, perm);
			cnt = (i == -1) ? cnt : cnt - 1;
		}

	}

	private static boolean check() {
		boolean result = true;
				
		for ( int i = 0 ; i < W ; i++) {
			int cnt = 1;
			for (int j = 1 ; j < D ; j++) {
				if( dummy[j-1][i] == dummy[j][i])
					cnt++;	
				else 
					cnt = 1;	
				if (cnt >= K) break;
			}
			if( cnt < K)
				return false;			
		}	
		return result;
	}

}

BF로 시도했으나 후반부 case에서 fail 되었다.

디버깅이 쉽지 않아, 코드를 검색해 보니 dfs로 충분히 풀 수 있는 문제였다.

문제를 해결하기 위한 아이디어에는 차이가 없었으나, 구현에서 dfs를 적용하는 방식에 있어 아직도 부족함을 느꼈다.

특히나 dfs의 인자로 prevD를 넘겨주고, 이를 for문 idx의 초기값으로 사용하여 다음 순서를 진행하는 코드는 멋졌다.

(Combination 구할 때도 이와 같은 방식을 사용)

참조 사이트 : https://namhandong.tistory.com/215

import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Solution {

	static int N;
	static int[][] map;
	private static boolean DBG = true;

	static int[] dx = { 1/* 오른쪽 아래 */, 1/* 왼쪽 아래 */, -1/* 왼쪽 위 */, -1/* 오른쪽 위 */ };
	static int[] dy = { 1, -1, -1, 1, };
	static boolean[][] visited;
	static boolean[] dessert;
	static int max;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			max=0;
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			StringTokenizer st = null;
			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());
				}

			}

			for (int i = 0; i < N - 2; i++) {
				for (int j = 1; j < N - 1; j++) {
					visited = new boolean[N][N];
					dessert = new boolean[101];
					visited[i][j] = true;
					dessert[map[i][j]] = true;
					dfs(1, i, j, i, j, 0);
				}
			}

			if (max == 0)
				max = -1;

			System.out.println("#" + test_case + " " + max);

		}

		System.out.println(sb);

	}

	private static void dfs(int cnt, int r, int c, int initR, int initC, int prevD) {
		for (int i = prevD; i < 4; i++) {
			int nr = r + dx[i];
			int nc = c + dy[i];

			if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
				if ((nr == initR) && (nc == initC) && cnt > 2) {
					max = Math.max(max, cnt);
					return;
				}

				if (!visited[nr][nc] && !dessert[map[nr][nc]]) {
					visited[nr][nc] = true;
					dessert[map[nr][nc]] = true;
					dfs(cnt + 1, nr, nc, initR, initC, i);
					visited[nr][nc] = false;
					dessert[map[nr][nc]] = false;
				}
			}

		}

	}

}