글 읽기 - 반례 부탁드립니다!!

go1217jo 5년 전 0

저번에 질문을 올렸었는데 그 뒤로 코드를 고쳐서 게시판 내 댓글의 반례를 모두 입력했는데 전부 맞습니다. 하지만 틀렸다고 나오는군요...

읽어보라고 하시는 게시판글은 전부 읽었습니다.. 제발 도와주세요ㅠㅠㅠㅠ

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

public class Main {
	static int N, M;
	
	static int explore(int[][] map, int row, int column) {
		int min = -1;
		int[] results = new int[] {-1, -1, -1, -1};
		//if(row >= 0 && column >= 0 && row < N && column < M) {
		//	System.out.printf("row : %d, column : %d\n", row, column);
		//}
		// 도착했을 때
		if(row == N-1 && column == M-1)
			return 1;
		// 범위 밖으로 벗어낫을 때
		else if(row < 0 || column < 0 || row >= N || column >= M)
			return -1;
		// 벽이거나 왔던 곳일 때
		else if(map[row][column] == 0 || map[row][column] == -1)
			return -1;
		else {
			map[row][column] = -1;
			// 좌
			results[0] = explore(map, row, column-1);
			// 우
			results[1] = explore(map, row, column+1);
			// 상
			results[2] = explore(map, row-1, column);
			// 하
			results[3] = explore(map, row+1, column);
			
			min = results[0];
			for(int k=1; k<4; k++) {
				if(min < 0)
					min = results[k];
				else if(results[k] > 0 && min > results[k])
					min = results[k];
			}
		}
		
		if(min != -1) {
			//System.out.printf("row : %d, column : %d, min : %d\n", row, column, (min+1));
			map[row][column] = 2;
			return min + 1;
		}
		else {
			return -1;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
	    scan.nextLine();
		
		int[][] map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String line = scan.nextLine();
			for(int j=0; j<M; j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
			
		System.out.print(explore(map, 0, 0));
	}
}

djm03178 5년 전 0

이 문제는 엄청난 아이디어를 생각해야 하는 문제가 아니고, 매우 정형화되어 있는 BFS라는 알고리즘을 써서 풀도록 의도된 문제인데, 올바름을 증명할 수 없는 다른 방법으로 굳이 풀려고 하실 필요는 없습니다.

djm03178 5년 전 0

물론, 반례는 원하신다면 드릴 수 있습니다.

5 6
101111
111010
111111
111111
111111
output: 12
correct answer: 10

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

문제

문제

출처

ICPC

반례 부탁드립니다!!

go1217jo 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말