글 읽기 - 반례가 모두 맞는데 틀리네요ㅠ

edsa159 5년 전 0

재귀를 이용해서 구현을 하였고 인터넷에 나와있는 반례들을 찾아서 돌려보았는데 제가 찾은 반례들에 대해서는 모두 값들이 일치했습니다.

하지만 %진행이 되지도 않고 틀렸습니다가 뜹니다.

어디서 잘못된건지 알려주세요 ㅠㅜㅜ

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Maze maze = new Maze();
		maze.input();
	}
}

class Maze {
	int N;
	int M;
	Scanner sc = new Scanner(System.in);
	int[][] arr;
	final int visited = 2;
	int dx[] = { 0, 1, 0, -1 };
	int dy[] = { 1, 0, -1, 0 };
	int count = 0;

	public void input() {
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N + 1][M + 1];
		for (int i = 1; i <= N; i++) {
			String str = sc.next();
			for (int j = 1; j <= M; j++) {
				arr[i][j] = Character.getNumericValue(str.charAt(j - 1));
			}
		}
		findpath(1, 1);
		System.out.println(count);
	}

	public boolean findpath(int x, int y) {
		if (x == N && y == M) {
			count++;
			return true;
		} else {
			arr[x][y] = visited;
			for (int i = 0; i < 4; i++) {
				if (x + dx[i] > 0 && y + dy[i] > 0 && x + dx[i] <= N && y + dy[i] <= M) {//범위 확인
					if (arr[x + dx[i]][y + dy[i]] == 1) {
						//	System.out.println("x : " + (x + dx[i]) + " y : " + (y + dy[i]));
						count++;

						if (findpath(x + dx[i], y + dy[i])) {
							return true;
						} else
							count--;
					}
				}

			}
			return false;
		}
	}
}

djm03178 5년 전 1

DFS식으로 찾다가 끝을 발견한 순간 탐색을 종료하는 건 최적이라는 보장이 없습니다.

edsa159 5년 전 0

최단경로라는 조건을 생각하지 못했네요

bfs로 바꿔서 구현해야겠군요ㅠㅜ 감사합니다.

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

문제

문제

출처

ICPC

반례가 모두 맞는데 틀리네요ㅠ

edsa159 5년 전 0

djm03178 5년 전 1

edsa159 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말