글 읽기 - 샘플 인풋은 제대로 답이 나오는데 제출하면 계속 틀리네요.

bahamoth 6년 전 0

결과를 보면 맞게 풀었다고 생각이 됩니다.

샘플 인풋을 몇 가지 만들어봤는데 생각대로 잘 풀리거든요.

그런데 제출하면 계속 틀리다고 하네요.

무엇 때문인지 이유를 잘 모르겠습니다.

메인 로직은 76 ~ 160 line 만 보시면 됩니다.

import java.util.Scanner;

public class Main {
    int k;
    int h;
    int w;
    char[][] map;
    boolean[][][] isVisited;
    Point destination;

    void setUp() {
        Scanner scanner = new Scanner(System.in);
        k = scanner.nextInt();
        h = scanner.nextInt();
        w = scanner.nextInt();
        map = new char[h][w];
        isVisited = new boolean[h][w][k+1];
        for(int i=0;i<h;++i) {
            for(int j=0;j<w;++j)
                map[i][j] = scanner.nextInt()==1 ? '1' : '0';
        }
        for(int i=0 ; i<h ; ++i) {
            for (int j=0 ; j<w ; ++j) {
                for (int l=0 ; l<k+1 ; ++l) {
                    isVisited[i][j][l] = false;
                    if (i==0 && j==0)
                        isVisited[i][j][l] = true;
                }
            }
        }
        destination = new Point(w-1, h-1);
    }

    void setUp(boolean isTest) {
        if (isTest==false)
            setUp();
        else {
            k = 6;
            h = 10;
            w = 10;
            map = new char[h][w];
            isVisited = new boolean[h][w][k+1];
            map[0] = "0111".toCharArray();
            map[1] = "0011".toCharArray();
            map[2] = "1011".toCharArray();
            map[3] = "1110".toCharArray();

            map[0] = "0000000000".toCharArray();
            map[1] = "0111111110".toCharArray();
            map[2] = "0011111110".toCharArray();
            map[3] = "0111111110".toCharArray();
            map[4] = "0101111110".toCharArray();
            map[5] = "0111111110".toCharArray();
            map[6] = "0110111110".toCharArray();
            map[7] = "0111110110".toCharArray();
            map[8] = "0111011100".toCharArray();
            map[9] = "0000000010".toCharArray();

            for(int i=0 ; i<h ; ++i) {
                for (int j=0 ; j<w ; ++j) {
                    for (int l=0 ; l<k+1 ; ++l) {
                        isVisited[i][j][l] = false;
                        if (i==0 && j==0)
                            isVisited[i][j][l] = true;
                    }
                }
            }
            destination = new Point(w-1, h-1);
        }
    }

    //진입점
    int solve() {
        int horseMove = 0;
        int distance = 0;
        Queue<Point> searchQueue = new Queue<>();
        if (horseMove < k) {
            pickHorsePoints(new Point(0,0, horseMove+1), searchQueue);
        }
        pickPoints(new Point(0,0), searchQueue);

        return search(searchQueue, distance);
    }

    //원숭이가 움직일 수 있는 4지점
    Point[] points(Point position) {
        Point[] ret = {
                new Point(position.x-1, position.y, position.horseMove),
                new Point(position.x+1, position.y, position.horseMove),
                new Point(position.x, position.y-1, position.horseMove),
                new Point(position.x, position.y+1, position.horseMove)
        };
        return ret;
    }

    //말처럼 움직일 수 있는 8지점
    Point[] horsePoints(Point position) {
        Point[] ret = {
                new Point(position.x-1, position.y-2, position.horseMove),
                new Point(position.x-1, position.y+2, position.horseMove),
                new Point(position.x+1, position.y-2, position.horseMove),
                new Point(position.x+1, position.y+2, position.horseMove),
                new Point(position.x-2, position.y-1, position.horseMove),
                new Point(position.x-2, position.y+1, position.horseMove),
                new Point(position.x+2, position.y-1, position.horseMove),
                new Point(position.x+2, position.y+1, position.horseMove)
        };
        return ret;
    }

    //입력받은 position에서 원숭이처럼 움직일 수 있는 경로를 입력받은 queue에 적재
    void pickPoints(Point position, Queue sQueue) {
        Point[] points = points(position);

        for (int i=0 ; i<4 ; ++i) {
            if (points[i].x>=0 && points[i].x<w && points[i].y>=0 && points[i].y<h &&
                    isVisited[points[i].y][points[i].x][points[i].horseMove] == false &&
                    map[points[i].y][points[i].x] == '0' &&
                    !sQueue.find(points[i]))
                sQueue.enqueue(points[i]);
        }
    }

    //입력받은 position에서 말처럼 움직일 수 있는 경로를 입력받은 queue에 적재
    void pickHorsePoints(Point position, Queue sQueue) {
        Point[] hp = horsePoints(position);

        for (int i=0 ; i<8 ; ++i) {
            if (hp[i].x>=0 && hp[i].x<w && hp[i].y>=0 && hp[i].y<h &&
                    isVisited[hp[i].y][hp[i].x][hp[i].horseMove] == false &&
                    map[hp[i].y][hp[i].x] == '0' &&
                    !sQueue.find(hp[i]))
                sQueue.enqueue(hp[i]);
        }
    }

    int search(Queue<Point> sQueue, int distance) {
        //System.out.println("current sQueue: "+sQueue.toString());
        //더 이상 경로를 찾을 수 없으면 -1 리턴
        if (sQueue.count==0) {
            //System.out.println("cannot find path");
            return -1;
        }

        ++distance;
        Queue<Point> newSQueue = new Queue<>();
        //기존 queue 에 적재된 node 들을 순회하며 다음 steop의 경로를 찾기 위한 신규 queue 생성
        for (Point iter=sQueue.dequeue() ; iter!=null ; iter=sQueue.dequeue()) {
            //System.out.println("current: "+iter+", distance: "+distance);
            isVisited[iter.y][iter.x][iter.horseMove] = true;
            if (destination.isSamePoint(iter)) {
                //System.out.println("found path, distance: "+distance);
                return distance;
            }
            pickPoints(new Point(iter.x,iter.y, iter.horseMove), newSQueue);
            if (iter.horseMove < k) {
                pickHorsePoints(new Point(iter.x,iter.y, iter.horseMove+1), newSQueue);
            }
        }

        return search(newSQueue, distance);
    }

    public static void main(String... args) {
        Main sol = new Main();
        sol.setUp();
        System.out.println(sol.solve());
    }

    static class Point {
        int x;
        int y;
        int horseMove;
        public Point() {}
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int horseMove) {
            this.x = x;
            this.y = y;
            this.horseMove = horseMove;
        }

        @Override
        public String toString() {
            return "("+x+", "+y+")hm:"+horseMove+" ";
        }

        @Override
        public boolean equals(Object obj) {
            Point rhs = (Point)obj;
            return rhs.x==x&&rhs.y==y&&rhs.horseMove==horseMove ? true : false;
        }

        public boolean isSamePoint(Point p) {
            return p.x==x&&p.y==y ? true : false;
        }
    }

    static class Element<T> {
        Element<T> next;
        Element<T> prev;
        T value;

        public Element() {}
        public Element(T value) {
            this.value = value;
        }
    }

    static class Queue<T> {
        Element<T> last;
        Element<T> first;
        int count=0;

        void enqueue(T value) {
            Element<T> newLast = new Element(value);
            if (last!=null) {
                last.prev = newLast;
                newLast.next = last;
            } else {
                first = newLast;
            }
            last = newLast;
            ++count;
        }

        T dequeue() {
            if (first==null)
                return null;
            T ret = first.value;
            first = first.prev;
            --count;

            return ret;
        }

        boolean find(T value) {
            boolean ret = false;
            for(Element iter=last ; iter!=first ; iter=iter.next) {
                if (value.equals(iter.value)) {
                    ret = true;
                    break;
                }
            }
            if (first!=null && value.equals(first.value))
                ret = true;
            return ret;
        }

        @Override
        public String toString() {
            String ret = "";
            for (Element iter=last ; iter!=null ; iter=iter.next) {
                ret += iter.value.toString();
            }
            return ret;
        }
    }
}

kdk8361 6년 전 0

setUp()으로 입력이 제대로 안받아지는 것 같습니다. 최소한 예제는 입력해 보시고 제출하시는걸 추천합니다.

bahamoth 6년 전 0

171 line 의

setUp(true); 를

setUp(); 으로 바꾸면 입력은 잘 받아집니다.

kdk8361 6년 전 0

를 입력하면

map[0]에 0,0,0,1이 아닌 0만 입력되고 차례대로 map[1], map[2]에 하나씩 입력됩니다.

bahamoth 6년 전 0

입력값 사이에 빈칸이 있었네요. 알려주셔서 감사합니다. 소스 수정했어요.

여전히 오답이라고 나오는건 변함이 없네요. 어디가 잘못된건지...

bahamoth 6년 전 0

width 와 height 의 순서를 반대로 입력받았었네요. 해결되었습니다. 감사합니다.

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

문제

문제

출처

ICPC

샘플 인풋은 제대로 답이 나오는데 제출하면 계속 틀리네요.

bahamoth 6년 전 0

kdk8361 6년 전 0

bahamoth 6년 전 0

kdk8361 6년 전 0

bahamoth 6년 전 0

bahamoth 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말