글 읽기 - 반례도 다 맞는데 왜 계속 틀렸다고 뜰까요?

as00098 2년 전 0

안녕하세요 코드의 접근법은

귀신 구멍일 경우에는 입력 받을 때 미리 귀신 구멍에서 이동할 수 있는 곳으로 간선을 추가한 다음, 귀신 구멍과 묘지인 곳을 제외한 모든 좌표에서 상하좌우로 갈 수 있는 곳을 인접 리스트에 추가했습니다. 그 다음에 정점의 개수만큼 계속해서 모든 정점에서 나가는 간선들에 대해 도착정점까지의 최단거리를 갱신했는데요, 게시판에 있는 반례는 모두 통과하는데 계속 50퍼센트에서 틀렸다고 뜨네요.

도와주실 분 계신가요 ㅠ

package per.november.platinum;

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.System.in;

public class P3860 {
    static final int[][] dxDy = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    static int[][] map;
    static final int GRAVE = 3;
    static final int EMPTY = 0;
    static final int HOLE = 2;

    static ArrayList<Edge>[][] adjacentList;

    static class Edge {
        final int toX;
        final int toY;
        final int weight;

        public Edge(int toX, int toY, int weight) {
            this.toX = toX;
            this.toY = toY;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            StringTokenizer mapInfo = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(mapInfo.nextToken());//너비
            int H = Integer.parseInt(mapInfo.nextToken());//높이
            if (W == 0 && H == 0) break;
            int G = Integer.parseInt(br.readLine()); //묘비의 개수
            map = new int[H][W];
            adjacentList = new ArrayList[H][W];
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    adjacentList[i][j] = new ArrayList<>();
                }
            }
            //묘지를 입력받는다.
            while (G-- > 0) {
                StringTokenizer graveInfo = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(graveInfo.nextToken());
                int y = Integer.parseInt(graveInfo.nextToken());
                map[y][x] = GRAVE;

            }
            int E = Integer.parseInt(br.readLine()); //귀신 구멍의 수
            while (E-- > 0) {
                StringTokenizer holeInfo = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(holeInfo.nextToken());
                int y = Integer.parseInt(holeInfo.nextToken());
                int x1 = Integer.parseInt(holeInfo.nextToken());
                int y1 = Integer.parseInt(holeInfo.nextToken());
                int T = Integer.parseInt(holeInfo.nextToken());
                map[y][x] = HOLE;
                //귀신 구멍의 경우 바로 간선을 추가한다.
                adjacentList[y][x].add(new Edge(x1, y1, T));
            }
            makeAdjacentList(W, H);
            int ret = solution(W, H);
            if (ret == INF)
                sb.append("Impossible").append("\n");
            else if (ret == -1) {
                sb.append("Never").append("\n");
            } else {
                sb.append(ret).append("\n");
            }
        }
        System.out.print(sb);
    }


    static void makeAdjacentList(int W, int H) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                //현재 지점이 묘비거나 귀신 구멍일 경우는 간선을 추가하지 않는다.
                if (map[i][j] == GRAVE || map[i][j] == HOLE) continue;
                //현재 지점이 도착 지점일 경우에 간선을 추가하지 않는다.
                if (i == H - 1 && j == W - 1) continue;
                for (int[] move : dxDy) {
                    int X = j + move[0];
                    int Y = i + move[1];
                    if (canVisit(X, Y, W, H) && map[Y][X] != GRAVE) {
                        adjacentList[i][j].add(new Edge(X, Y, 1));
                    }
                }
            }
        }
    }

    static final int INF = 1987654321;

    static int solution(int W, int H) {
        int[][] dist = new int[H][W];
        for (int i = 0; i < H; i++) {
            Arrays.fill(dist[i], INF);
        }
        //시작 지점의 거리를 0으로 표시
        dist[0][0] = 0;
        int numberOfVertex = H * W;
        for (int n = 0; n < numberOfVertex; n++) {
            boolean isUpdate = false;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    for (Edge edge : adjacentList[i][j]) {
                        if (dist[i][j] != INF && dist[edge.toY][edge.toX] > dist[i][j] + edge.weight) {
                            dist[edge.toY][edge.toX] = dist[i][j] + edge.weight;
                            isUpdate = true;
                        }
                    }
                }
            }
            //음의 사이클이 존재한다면 바로 -1 반환
            if (isUpdate && n == numberOfVertex - 1) {
                return -1;
            }
        }
        //음의 사이클이 존재하지 않는다면, 도착지점까지의 거리 반환
        return dist[H - 1][W - 1];
    }

    static boolean canVisit(int x, int y, int W, int H) {
        return (x >= 0 && y >= 0 && x < W && y < H);
    }
}

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

문제

문제

출처

ICPC

반례도 다 맞는데 왜 계속 틀렸다고 뜰까요?

as00098 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말