글 읽기 - 스도미노쿠 50%에서 틀립니다.....

hjm7091 4년 전 0

뭘 놓치고 있는 걸까요...ㅠㅠ

Class

Point : 행과 열의 좌표 값을 가지고 있음

Domino : 두 개의 값을 가지고 있음, 객체 비교를 위해 equals(), hashCode() 재정의

Method

init() : 각 변수들을 초기화

getPoint() : 알파벳과 숫자로 이루어진 문자열을 받아서 가공후 Point로 반환

fillPuzzle() : 퍼즐에 값을 채우고, 스도쿠 규칙을 만족하는지 검사하는 row, col, rect 배열에 값 할당

emptyPuzzle() : fillPuzzle()과 반대의 작업을 함

getRectNum() : 해당 좌표가 속하는 작은 사각형의 번호 반환

addDomino() : (작은 수, 큰 수) 순서에 맞도록 도미노를 설정 후 dominos 리스트에 넣음

makeUnUsedDomino() : 36가지 도미노를 순열을 이용하여 만들면서 dominos 리스트가 이미 포함하고 있는 도미노이면 dominos 리스트에서 제거하고 포함하고 있지 않은 도미노이면 리스트에 넣음

start() : dominos 리스트에 있는 도미노를 놓을 수 있는 모든 경우의 수를 만듬

canPut() : 범위 체크와 값 존재 여부 체크

putDomino() : 도미노를 놓는다.

removeDomino() : 도미노를 제거한다.

breakRule() : 스도쿠 규칙 확인, 스도쿠 규칙을 만족하지 않으면 true, 만족하면 false

printPuzzle() : puzzle 배열 출력

printDominos() : dominos 리스트 출력

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

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

class Domino {
	int v1, v2;
	public Domino(int v1, int v2) {
		this.v1 = v1;
		this.v2 = v2;
	}
	
	@Override
	public boolean equals(Object obj) {
		if(!(obj instanceof Domino))
			return false;
		Domino domino = (Domino) obj;
		if((domino.v1 == v1 && domino.v2 == v2) ||
				(domino.v1 == v2 && domino.v2 == v1))
			return true;
		return false;
	}
	
	@Override
	public int hashCode() {
		return Integer.toString(v1).hashCode() + Integer.toString(v2).hashCode();
	}
	
	@Override
	public String toString() {
		return "[" + v1 + "," + v2 + "]";
	}
}

public class Main {
	
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	static final int MAX_SIZE = 9;
	static final int MAX_NUM = 10;
	static int[][] puzzle;
	static boolean[][] row, col, rect;
	static List<Domino> dominos = new ArrayList<Domino>();
	static boolean[] visitedDomino;
	static int[] dx = {0,1};
	static int[] dy = {1,0};
	static boolean flag;
	
	public static void main(String[] args) throws IOException {
		playGame();
	}
	
	private static void playGame() throws IOException{
		int gameNum = 1;
		while(true) {
			N = Integer.parseInt(input.readLine());
			if(N == 0)
				break;
			init();
			makeAllDomino(0, new ArrayList<Integer>());
			output.write("Puzzle " + gameNum + "\n");
			start(0);
			gameNum++;
		}
		output.flush();
		input.close();
		output.close();
	}
	
	private static void init() throws IOException{
		flag = false;
		puzzle = new int[MAX_SIZE][MAX_SIZE];
		row = new boolean[MAX_SIZE][MAX_NUM];
		col = new boolean[MAX_SIZE][MAX_NUM];
		rect = new boolean[MAX_SIZE][MAX_NUM];
		dominos.clear();
		visitedDomino = new boolean[36 - N];
		
		for(int i = 0; i < N; i++) {
			String[] info = input.readLine().split(" ");
			Point p = getPoint(info[1]);
			fillPuzzle(Integer.parseInt(info[0]), p.x, p.y);
			p = getPoint(info[3]);
			fillPuzzle(Integer.parseInt(info[2]), p.x, p.y);
			addDomino(info[0], info[2]);
		}
		
		String[] info = input.readLine().split(" ");
		for(int i = 0; i < info.length; i++) {
			Point p = getPoint(info[i]);
			fillPuzzle(i+1, p.x, p.y);
		}
	}
	
	private static Point getPoint(String coord) {
		int x = coord.charAt(0) - 'A';
		int y = (coord.charAt(1) - '0') - 1;
		return new Point(x, y);
	}
	
	private static void fillPuzzle(int value, int x, int y) {
		puzzle[x][y] = value;
		row[x][value] = true;
		col[y][value] = true;
		rect[getRectNum(x, y)][value] = true;
	}
	
	private static void emptyPuzzle(int value, int x, int y) {
		puzzle[x][y] = 0;
		row[x][value] = false;
		col[y][value] = false;
		rect[getRectNum(x, y)][value] = false;
	}
	
	private static int getRectNum(int x, int y) {
		return ((x / 3) * 3) + (y / 3);
	}
	
	private static void addDomino(String info1, String info2) {
		int v1 = Integer.parseInt(info1);
		int v2 = Integer.parseInt(info2);
		if(v1 < v2)
			dominos.add(new Domino(v1, v2));
		else if(v1 > v2)
			dominos.add(new Domino(v2, v1));
	}
	
	private static void makeAllDomino(int start, List<Integer> nums) throws IOException {
		if(nums.size() == 2) {
			Domino domino = new Domino(nums.get(0), nums.get(1));
			if(dominos.contains(domino)) 
				dominos.remove(domino);
			else
				dominos.add(domino);
			return;
		}
		for(int i = start + 1; i <= 9; i++) {
			nums.add(i);
			makeAllDomino(i, nums);
			nums.remove(nums.size() - 1);
		}
	}
	
	private static void start(int now) throws IOException {
		if(now == 81) {
			if(flag)
				return;
			
			flag = true;
			printPuzzle();
			return;
		}
		Point p = new Point(now / MAX_SIZE, now % MAX_SIZE);
		if(puzzle[p.x][p.y] != 0) {
			start(now + 1);
		} else {
			for(int i = 0; i < dominos.size(); i++) {
				if(!visitedDomino[i]) {
					Domino domino = dominos.get(i);
					visitedDomino[i] = true;
					
					for(int dir = 0; dir < 2; dir++) {
						Point np = new Point(p.x + dx[dir], p.y + dy[dir]);
						if(canPut(np.x, np.y)) { //배치 가능하고 
							if(!breakRule(p, domino.v1) && !breakRule(np, domino.v2)) { //스도쿠 룰을 어기지 않는다면
								putDomino(p, np, domino.v1, domino.v2);
								start(now + 1);
								removeDomino(p, np, domino.v1, domino.v2);
							}
							
							if(!breakRule(p, domino.v2) && !breakRule(np, domino.v1)) { //스도쿠 룰을 어기지 않는다면
								putDomino(p, np, domino.v2, domino.v1);
								start(now + 1);
								removeDomino(p, np, domino.v2, domino.v1);
							}
						}
					}
					
					visitedDomino[i] = false;
				}
			}
		}
	}
	
	private static boolean canPut(int x, int y) {
		if(x < 0 || x > MAX_SIZE - 1 || y < 0 || y > MAX_SIZE - 1)
			return false;
		if(puzzle[x][y] != 0)
			return false;
		return true;
	}
	
	private static void putDomino(Point p1, Point p2, int v1, int v2) {
		fillPuzzle(v1, p1.x, p1.y);
		fillPuzzle(v2, p2.x, p2.y);
	}
	
	private static void removeDomino(Point p1, Point p2, int v1, int v2) {
		emptyPuzzle(v1, p1.x, p1.y);
		emptyPuzzle(v2, p2.x, p2.y);
	}
	
	private static boolean breakRule(Point p, int value) {
		if(row[p.x][value] || col[p.y][value] || rect[getRectNum(p.x, p.y)][value])
			return true;
		return false;
	}
	
	private static void printPuzzle() throws IOException {
		for(int x = 0; x < MAX_SIZE; x++) {
			for(int y = 0; y < MAX_SIZE; y++) {
				output.write(puzzle[x][y] + " ");
			}
			output.write("\n");
		}
	}

}

hjm7091 4년 전 0

아... 출력을 잘못했네요 ㅠㅠ

50%에서 틀리길래 로직이 잘못된 줄 알았는데 단순히 출력문제였습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

스도미노쿠 50%에서 틀립니다.....

hjm7091 4년 전 0

hjm7091 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말