글 읽기 - 1799번 비숍 문제 질문 드립니다.

ikth6001 4년 전 0

안녕하세요 알고리즘 초보입니다. 비숍 문제 풀고 있는데요.. 왜 틀렸는지 원인을 모르겠네요...

조언 부탁 드립니다.

알고리즘은 간단한 백트래킹? 으로 이중 루프로 체스판을 돌며 비숍을 놓을 수 있으면 놓은 후 재귀로 DFS를 하는 방법입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main {

	public static void main(String[] args) {
		try(BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out))) {
			
			Main m= new Main();
			m.solution(br, bw);
			bw.flush();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void solution(BufferedReader br, BufferedWriter bw) throws NumberFormatException, IOException {
		
		int n= Integer.valueOf(br.readLine());
		int[][] chessMap= new int[n][n];
		
		for(int i=0; i<n; i++) {
			String[] row= br.readLine().split(" ");
			for(int j=0; j<n; j++) {
				chessMap[i][j]= Integer.valueOf(row[j]);
			}
		}
		
		int max= solution(chessMap, new boolean[n*2], new boolean[n*2], 0, 0);
		bw.write(String.valueOf(max));
	}
	
	private int solution(int[][] chessMap, boolean[] ltrb, boolean[] lbrt, int h, int w) {

		int n= chessMap.length;
		
		if(w == n) {
			w= 0;
			h++;
		}
		
		int max= 0;
		for(int i=h; i<n; i++) {
			
			for(int j=w; j<n; j++) {
				
				int ltrbIdx= i-j+n-1;
				int lbrtIdx= i+j;
				
				if(chessMap[i][j] == 0 || ltrb[ltrbIdx] || lbrt[lbrtIdx]) {
					continue;
				}
				
				ltrb[ltrbIdx]= true;
				lbrt[lbrtIdx]= true;
				
				int cnt= 1 + solution(chessMap, ltrb, lbrt, i, j+1);
				max= max < cnt ? cnt : max;
				
				ltrb[ltrbIdx]= false;
				lbrt[lbrtIdx]= false;
			}
		}
		
		return max;
	}
}

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

문제

문제

출처

ICPC

1799번 비숍 문제 질문 드립니다.

ikth6001 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말