글 읽기 - 100%에서 틀립니다. Java, 다익스트라 사용했습니다.

clcell3 3년 전 0

N행 M열로 입력받았습니다.

logic:

처음에 0,0 을 우선순위 큐에 밀어넣고 가중치를 0으로 설정합니다.(시작 지점과 끝 지점은 벽이 없음이 보장되므로)

이후 dn, dm 배열을 이용하여 현재 위치를 기준으로 상하좌우를 체크하여 방문하지 않은 곳이라면 우선순위 큐에 밀어넣습니다.

이를 반복하다 (N-1, M-1)에 도착하면 현재 가중치를 출력합니다.

질문글에 있는 테스트 케이스

case1

input:

1 1

output:

case2

input:

3 1

0 1 0

output:

위의 케이스 등등 일반적인 것들은 모두 확인해봤습니다.

100%까지 보여준 후 틀렸다고나옵니다.

논리에 오류가 있는건지 특정 케이스에서 걸리는 것 같은데, 고수님들의 조언이 필요합니다.

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

/**
 * Created by Cella.
 * User: clcell1646
 * Date: 2020/07/07
 * Time: 3:53 오후
 */

class Point1261 implements Comparable<Point1261> {
    int n, m, weight;
    public Point1261(int n, int m, int weight) {
        this.n = n;
        this.m = m;
        this.weight = weight;
    }

    @Override
    public int compareTo(Point1261 p) {
        return this.weight - p.weight;
    }
}


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()), N = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M]; // true == wall;
        boolean[][] visit = new boolean[N][M];
        for(int i = 0; i<N; i++) {
            String str = br.readLine();
            for(int j = 0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        int[] dn = { 0, 0, -1, 1 };
        int[] dm = { 1, -1, 0, 0 };

        PriorityQueue<Point1261> pQueue = new PriorityQueue<>();
        pQueue.add(new Point1261(0, 0, 0)); // (0, 0) to (N-1, M-1)
        visit[0][0] = true;
        while(!pQueue.isEmpty()) {
            Point1261 point = pQueue.poll();
            for(int i = 0; i<4; i++) {
                int tn = point.n + dn[i];
                int tm = point.m + dm[i];
                if(tn>=0&&tn<N&&tm>=0&&tm<M&&!visit[tn][tm]) {
                    visit[tn][tm] = true;
                    pQueue.add(new Point1261(tn, tm, map[tn][tm]+point.weight));
                    if(tn == N-1 && tm == M-1) {
                        System.out.println(point.weight);
                        return;
                    }
                }
            }
        }
    }
}

shg9411 3년 전 1

N-1, M-1과의 비교는 꺼낼 때 하셔야 정답인지 확신할 수 있지 않을까요?

map[tn][tm]이 1일 때와 0일 때를 신경 쓰지 않고 출력하시면 답임을 확신할 수 없습니다.

clcell3 3년 전 1

감사합니다.

다익스트라 구현 자체가 틀렸었네요..!

좋은하루 되세요 :)

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

문제

문제

출처

ICPC

100%에서 틀립니다. Java, 다익스트라 사용했습니다.

clcell3 3년 전 0

shg9411 3년 전 1

clcell3 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말