글 읽기 - 도와주십시오...

cuhcuh1 5년 전 0

안녕하십니까...
고수님 들의 도움이 필요해서 이렇게 질문 드립니다.

풀이 방식은 BFS를 이용해 visit라는 배열에 명령어 숫자를 기록해 가면서 도착 지점에 도달하면 loop를 빠져나와 답을 출력하는 방식으로 했습니다.

visit이라는 배열은 map 사이즈에 4방향을 모두 저장할 수 있고, 같은 방향을 바라보는 같은 지점은 이전에 도달 했을 경우가 명령어가 더 작을 경우기 때문에 다시 search 하지 않게 했습니다.

여러 예제 input을 만들어서 테스트를 해 봤지만 정답은 제대로 나오는 것 같은데 틀리다고 나옵니다.
어느 부분을 제가 빠트리고 고려하지 않았는지 궁금합니다.

도와주십시오 ㅠㅠㅠ

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

class Main {

    static int n, m;
    static int[][] map;
    static int[][][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk=new StringTokenizer(br.readLine());

        n=Integer.parseInt(tk.nextToken());
        m=Integer.parseInt(tk.nextToken());
        map=new int[n][m];
        visit=new int[5][n][m];

        for(int i=0; i<5; i++) {
            for(int j=0; j<n; j++) {
                Arrays.fill(visit[i][j], -1);
            }
        }

        for(int i=0; i<n; i++) {
            tk=new StringTokenizer(br.readLine());
            for(int j=0; tk.hasMoreTokens(); j++) {
                map[i][j]=Integer.parseInt(tk.nextToken());
            }
        }

        tk=new StringTokenizer(br.readLine());
        robot start=new robot(Integer.parseInt(tk.nextToken())-1, Integer.parseInt(tk.nextToken())-1, Integer.parseInt(tk.nextToken()), 0);
        tk=new StringTokenizer(br.readLine());
        robot end=new robot(Integer.parseInt(tk.nextToken())-1, Integer.parseInt(tk.nextToken())-1, Integer.parseInt(tk.nextToken()), 0);

        Queue<robot> qu=new LinkedList<robot>();
        qu.add(start);
        visit[start.dir][start.y][start.x]=0;

        while(!qu.isEmpty()) {
            // show();
            robot pos=qu.poll();

            if(end.compare(pos)) {
                break;
            }

            go(pos, qu);
            
            int nextDir=rotate(pos.dir, false);
            if(visit[nextDir][pos.y][pos.x]==-1) {
                visit[nextDir][pos.y][pos.x]=pos.com+1;
                qu.add(new robot(pos.y, pos.x, nextDir, pos.com+1));
            }
            nextDir=rotate(pos.dir, true);
            if(visit[nextDir][pos.y][pos.x]==-1) {
                visit[nextDir][pos.y][pos.x]=pos.com+1;
                qu.add(new robot(pos.y, pos.x, nextDir, pos.com+1));
            }
        }

        System.out.println(visit[end.dir][end.y][end.x]);
    }

    static void show() {
        for(int k=1; k<=4; k++) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    System.out.printf("%3d", visit[k][i][j]);
                }
                System.out.printf("\t\t");
                for(int j=0; j<m; j++) {
                    System.out.printf("%3d", map[i][j]);
                }
                System.out.println();
            }
            System.out.println();
        }
        System.out.println();
    }

    static int rotate(int dir, boolean turn) {
        int ret=-1;
        if(turn) {
            // to left
            switch(dir) {
                case 1: ret=4; break;
                case 2: ret=3; break;
                case 3: ret=1; break;
                case 4: ret=2; break;
            }
        } else {
            // to right
            switch(dir) {
                case 1: ret=3; break;
                case 2: ret=4; break;
                case 3: ret=2; break;
                case 4: ret=1; break;
            }
        }

        return ret;
    }

    static void go(robot pos, Queue<robot> qu) {
        switch(pos.dir) {
            case 1:
                for(int i=pos.x+1; i<Math.min(m, pos.x+4); i++) {
                    if(visit[pos.dir][pos.y][i]==-1 && map[pos.y][i]==0) {
                        visit[pos.dir][pos.y][i]=pos.com+1;
                        qu.add(new robot(pos.y, i, pos.dir, pos.com+1));
                    } else {
                        break;
                    }
                }
                break;
            case 2:
                for(int i=pos.x-1; i>=Math.max(0, pos.x-3); i--) {
                    if(visit[pos.dir][pos.y][i]==-1 && map[pos.y][i]==0) {
                        visit[pos.dir][pos.y][i]=pos.com+1;
                        qu.add(new robot(pos.y, i, pos.dir, pos.com+1));
                    } else {
                        break;
                    }
                }
                break;
            case 3:
                for(int i=pos.y+1; i<Math.min(n, pos.y+4); i++) {
                    if(visit[pos.dir][i][pos.x]==-1 && map[i][pos.x]==0) {
                        visit[pos.dir][i][pos.x]=pos.com+1;
                        qu.add(new robot(i, pos.x, pos.dir, pos.com+1));
                    } else {
                        break;
                    }
                }
                break;
            case 4:
                for(int i=pos.y-1; i>=Math.max(0, pos.y-3); i--) {
                    if(visit[pos.dir][i][pos.x]==-1 && map[i][pos.x]==0) {
                        visit[pos.dir][i][pos.x]=pos.com+1;
                        qu.add(new robot(i, pos.x, pos.dir, pos.com+1));
                    } else {
                        break;
                    }
                }
                break;
        }
    }
}

class robot {

    int y, x, dir, com;

    robot(int y, int x, int dir, int com) {
        this.y=y;
        this.x=x;
        this.dir=dir;
        this.com=com;
    }

    public boolean compare(robot a) {
        if(y==a.y && x==a.x && dir==a.dir) {
            return true;
        } else {
            return false;
        }
    }
}

3587jjh 5년 전 2

go함수에서 진행 도중에 방문된 칸을 만나면 바로 break 하셨는데

그 칸을 넘어서 진행할 수도 있어요

cuhcuh1 5년 전 0

@3587jjh

답변 감사드립니다.
정말 생각지도 못한 케이스였습니다.

이미 한번 방문한 지점에서 회전과 전진을 다 하기 때문에 이미 방문한 지점을 만나면 근처 지점은 이미 다 방문 했을 수 있다고 생각해서 break를 넣었던 것이었는데 잘못 생각했었네요.

덕분에 해결할 수 있었습니다. 감사합니다.

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

문제

문제

출처

ICPC

도와주십시오...

cuhcuh1 5년 전 0

3587jjh 5년 전 2

cuhcuh1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말