글 읽기 - 도저히 틀린 원인을 못찾겠습니다..

sbj8388 5년 전 0

도저히 틀린원인을 못찾겠네요...
샘플예제는 제대로 나오고 예외할만한 것도 어느정도 다 넣어봤는데,
어디서 틀렸는지를 모르겠습니다 ㅜㅜ
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
	static int Y ;
	static int X ;
	static int ans = Integer.MAX_VALUE;
	static int arr[][];

	static String LEFT = "left";
	static String RIGHT = "right";
	static String UP = "up";
	static String DOWN = "down";

	static String type1[] = { RIGHT, DOWN, LEFT, UP };

	static String type2[] = { LEFT, RIGHT, 
						 	UP, DOWN };
	
	static String type3[] = {  
							UP, RIGHT, 
							RIGHT, DOWN, 
							DOWN, LEFT,
							LEFT, UP};

	static String type4[] = { LEFT, UP, RIGHT, 
							  UP, RIGHT, DOWN, 
							  RIGHT, DOWN, LEFT, 
							  DOWN, LEFT, UP };
	static String type5[] = { LEFT, DOWN, RIGHT, UP };
	static ArrayList<node> list = new ArrayList<>();
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Y = in.nextInt();
		X = in.nextInt();
		arr = new int[Y][X];

		for (int y = 0; y < Y; y++) {
			for (int x = 0; x < X; x++) {
				arr[y][x] = in.nextInt();
				if (arr[y][x] != 0 && arr[y][x] != 6) {
					list.add(new node(x, y, arr[y][x]));
				}
			}
		}
		int N = list.size();
		int start = 0;
		
		int[][] temp = copy(arr);
		ans = Math.min(ans, count(arr));
		
		go2(temp, start, N, 0, 0, 0, 0, 0);
		
		System.out.println(ans);
		
	}
	public static void go2(int[][] board, int index, int N,
							int tindex1, int tindex2, int tindex3, int tindex4, int tindex5) {
		if(index == N) {
			ans = Math.min(ans, count(board));
			return;
		}
		node n = list.get(index);
		switch(n.type){
			case 1:
				for(int i=tindex1; i<type1.length; i++) {
					int temp[][] = copy(board);
					go(board, type1[i], n.x, n.y, 1);
					go2(board, index + 1, N, i, tindex2, tindex3, tindex4, tindex5);
					board = copy(temp);
				}
				break;
			case 2:
				for(int i=tindex2; i<type2.length; i+=2) {
					int temp[][] = copy(board);
					go(board, type2[i], n.x, n.y, 2);
					go(board, type2[i+1], n.x, n.y, 2);
					go2(board, index + 1, N, tindex1, i, tindex3, tindex4, tindex5);
					board = copy(temp);
				}
				break;
			case 3:
				for(int i=tindex3; i<type3.length; i+=2) {
					int temp[][] = copy(board);
					go(board, type3[i], n.x, n.y, 3);
					go(board, type3[i+1], n.x, n.y, 3);
					go2(board, index + 1, N, tindex1, tindex2, i, tindex4, tindex5);
					board = copy(temp);
				}
				break;
			case 4:
				for(int i=tindex4; i<type4.length; i+=3) {
					int temp[][] = copy(board);
					go(board, type4[i], n.x, n.y, 4);
					go(board, type4[i+1], n.x, n.y, 4);
					go(board, type4[i+2], n.x, n.y, 4);
					go2(board, index + 1, N, tindex1, tindex2, tindex3, i, tindex5);
					board = copy(temp);
				}
				break;
			case 5:
				int temp[][] = copy(board);
				go(board, type5[0], n.x, n.y, 5);
				go(board, type5[1], n.x, n.y, 5);
				go(board, type5[2], n.x, n.y, 5);
				go(board, type5[3], n.x, n.y, 5);
				go2(board, index + 1, N, tindex1, tindex2, tindex3, tindex4, tindex5);
				board = copy(temp);
				break;
		}
	}
	public static void go(int[][] board, String dir, int x, int y, int v) {
		if(x < 0 || x >= X || y < 0 || y >= Y)
			return;
		
		int nx;
		int ny;
		switch (dir) {
		case "left":
			nx = x - 1;
			ny = y;
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 6) {
				return;
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 0) {
				board[ny][nx] = v;
				go(board, dir, nx, ny, v);
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && 1 <= arr[ny][nx] && arr[ny][nx] <= 5) {
				board[ny][nx] = board[y][x];
				go(board, dir, nx, ny, v);
			}
			break;
		case "right":
			nx = x + 1;
			ny = y;
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 6) {
				return;
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 0) {
				board[ny][nx] = v;
				go(board, dir, nx, ny, v);
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && 1 <= arr[ny][nx] && arr[ny][nx] <= 5) {
				board[ny][nx] = board[y][x];
				go(board, dir, nx, ny, v);
			}
			
			break;
		case "up":
			nx = x;
			ny = y - 1;
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 6) {
				return;
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 0) {
				board[ny][nx] = v;
				go(board, dir, nx, ny, v);
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && 1 <= arr[ny][nx] && arr[ny][nx] <= 5) {
				board[ny][nx] = board[y][x];
				go(board, dir, nx, ny, v);
			}
			break;
		case "down":
			nx = x;
			ny = y + 1;
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 6) {
				return;
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && arr[ny][nx] == 0) {
				board[ny][nx] = v;
				go(board, dir, nx, ny, v);
			}
			if(nx >= 0 && nx < X && ny >= 0 && ny < Y && 1 <= arr[ny][nx] && arr[ny][nx] <= 5) {
				board[ny][nx] = board[y][x];
				go(board, dir, nx, ny, v);
			}
			break;
		}
	}

	public static int count(int[][] board) {
		int result = 0;
		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				if (board[i][j] == 0)
					result++;
			}
		}
		return result;
	}

	public static int[][] copy(int[][] board) {
		int temp[][] = new int[Y][X];
		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				temp[i][j] = board[i][j];
			}
		}
		return temp;
	}

	static class node {
		int y;
		int x;
		int type;

		public node(int x, int y, int type) {
			this.x = x;
			this.y = y;
			this.type = type;
		}
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

도저히 틀린 원인을 못찾겠습니다..

sbj8388 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
