글 읽기 - 질문검색에 있는 반례들 다 통과하는데 96%에서 실패가 나옵니다 ㅠㅠ

tmakdlf2770 4년 전 0

왜 96%에서 실패가나올까요??ㅠㅠ

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
		static int map[][];
		static int N;
		static int M;
		static int cnt;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		for(int i =0 ; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		cnt=0;
		bfs(0,0);
		System.out.println(cnt);

	}
	static int[][] dir = {{1,0},{0,1},{1,1}};
	private static void bfs(int x,int y) {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(x,y));
		int max[][]= new int[N][M];
		max[0][0]=map[0][0];
		while(!q.isEmpty()) {
			Pair p = q.poll();
			for(int i=0;i<3;i++) {
				int tx = p.x+dir[i][0];
				int ty = p.y+dir[i][1];
				if(tx<0 || ty<0 || tx>=N || ty>=M) continue;
				if(map[tx][ty]+max[p.x][p.y]>max[tx][ty]) {
					max[tx][ty]=map[tx][ty]+max[p.x][p.y];
					q.add(new Pair(tx, ty));
				}
			}
		}
		cnt = max[N-1][M-1];
		
	}
	static class Pair{
		private int y,x;

		Pair(int x, int y){
			this.y = y;
			this.x = x;
		}
	}
}

이 글의 바로 아래에 있는 질문 https://www.acmicpc.net/board/... 도 96%에서 틀렸다고 합니다. 그 답변에서 말하는 내용을 보면, '방문하지 않았을 때 가는' 조건을 잘못 적은 것을 지적하고 있습니다. 그리고 코드를 보면 질문자님의 코드와 마찬가지로 거리가 가까워질 때 큐에 넣는 부분은 제대로 구현되어 있습니다. 그럼 이게 무슨 뜻일까요? 거리가 갱신되지 않았어도 가봐야 하는 경우가 있다는 것입니다.

https://ideone.com/pRIgwn

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

문제

문제

출처

ICPC

질문검색에 있는 반례들 다 통과하는데 96%에서 실패가 나옵니다 ㅠㅠ

tmakdlf2770 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말