글 읽기 - 1799번 다음 탐색할 인덱스 계산

dptmf06 3년 전 0

로직이 맞은 분들과 다를 것이 없어보입니다. 인덱스를 계산하는 부분(line41~line47)에서 틀려서 어떤 경우를 건너뛰고 있는 걸까요?(9%에서 틀립니다.)

게시판에 있는 반례는 모두 돌려보니 답이 나왔습니다. 혹시 제가 놓친 부분이 있는지, 아니면 인덱스 계산이 틀렸는지 봐주시면 정말 감사할 것 같습니다!

import java.io.*;
import java.util.*;

public class Main {
	static int N, max0, max1;
	static int[][] board; // 원래값을 보존해야하므로 변형 X
	static boolean[][] visited;
	// 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
	static int[] dx = {-1, -1, 1, 1};
	static int[] dy = {-1, 1, -1, 1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		max0 = 0;
		max1 = 0;
		
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 0부터 시작하는 경우
		visited = new boolean[N][N];
		search(0, 0, 0, 0);
		// 1부터 시작하는 경우
		visited = new boolean[N][N];
		search(0, 1, 0, 1);
		
		System.out.println(max0+max1);
	}// end of main
	static void search(int x, int y, int cnt, int flag) {
		// 종료조건
		if(flag == 0) {
			max0 = Math.max(cnt, max0);
		}else {
			max1 = Math.max(cnt, max1);
		}
		if(y >= N*N)return;
		int tmpY = (y)%N;
		// 놓을 수 있어서 놓은 경우
		if(ableToPut(x, tmpY)) {
			visited[x][tmpY] = true; //@@@@@
			search((y+2)/N, y+2, cnt+1, flag);
			visited[x][tmpY] = false; //@@@@@
		}
		
		// 안놓는 경우
		search((y+2)/N, y+2, cnt, flag);
	}
	
	static boolean ableToPut(int cx, int cy) {
		if(board[cx][cy] == 0)return false; //@@@@@
		for(int i=0;i<4;i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			
			while(nx < N && nx >= 0 && ny < N && ny >= 0) { // 범위 내에 있는 동안
				if(visited[nx][ny]) return false; //  방문했으면 - 이미 비숍 놓여있으면 //@@@@@
				nx += dx[i];
				ny += dy[i];
			}
		}
		return true;
	}
}

plan222 3년 전 2

반례

1 1

Answer: 2

Output: 4

처음 방문 하는 곳의 visited를 고려해주세요

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

문제

문제

출처

ICPC

1799번 다음 탐색할 인덱스 계산

dptmf06 3년 전 0

plan222 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말