글 읽기 - 자바 89% 시간초과 원인 좀 알려주시면 감사하겠습니다.

tmddjs210 3년 전 0

89%에서 계쏙 시간초과가 뜨는데 원인을 모르겠습니다. ㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    private static int N;
    private static int[][] map;
    private static int[] garoDr = {0, 1};
    private static int[] garoDc = {1, 1};
    private static int[] seroDr = {1, 1};
    private static int[] seroDc = {0, 1};
    private static int[] degakDr = {1, 0, 1};
    private static int[] degakDc = {0, 1, 1};
    private static int answer = 0;
    private static int GARO = 0;
    private static int SERO = 1;
    private static int DEGAK = 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        bfs();
        System.out.println(answer);
    }

    private static void bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(0, 1, GARO));
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int r = point.r;
            int c = point.c;
            int prev = point.prev;
            if (r == N - 1 && c == N - 1) {
                answer++;
                continue;
            }
            if (prev == GARO) {
                moveTwoWay(queue, r, c, garoDr, garoDc, GARO);
            } else if (prev == SERO) {
                moveTwoWay(queue, r, c, seroDr, seroDc, SERO);
            } else if (prev == DEGAK) {
                for (int i = 0; i < 3; i++) {
                    int r2 = r + degakDr[i];
                    int c2 = c + degakDc[i];
                    if (i == 0) { //아래이동
                        if (r2 < N && c2 >= 0 && c2 < N && map[r2][c2] == 0) {
                            queue.offer(new Point(r2, c2, SERO));
                        }
                    } else if (i == 1) { //우측이동
                        if (r2 < N && c2 >= 0 && c2 < N && map[r2][c2] == 0) {
                            queue.offer(new Point(r2, c2, GARO));
                        }
                    } else {//대각선 이동
                        if (r2 < N && c2 < N && map[r2][c2] == 0 && map[r2 - 1][c2] == 0 && map[r2][c2 - 1] == 0) {
                            queue.offer(new Point(r2, c2, DEGAK));
                        }
                    }
                }
            }
        }
    }

    private static void moveTwoWay(Queue<Point> queue, int r, int c, int[] seroDr, int[] seroDc, int sero) {
        for (int i = 0; i < 2; i++) {
            int r2 = r + seroDr[i];
            int c2 = c + seroDc[i];
            if (i == 0) {
                if (r2 < N && c2 >= 0 && c2 < N && map[r2][c2] == 0) {
                    queue.offer(new Point(r2, c2, sero));
                }
            } else {  //대각선 이동
                if (r2 < N && c2 < N && map[r2][c2] == 0 && map[r2 - 1][c2] == 0 && map[r2][c2 - 1] == 0) {
                    queue.offer(new Point(r2, c2, DEGAK));
                }
            }
        }
    }


    private static class Point {
        int r;
        int c;
        int prev;

        Point(int r, int c, int prev) {
            this.r = r;
            this.c = c;
            this.prev = prev;
        }
    }
}

cds06126 2년 전 1

같은 로직을 cpp으로 짜면, 풀립니다.

Java의 경우엔 DP로 푸는 방식이 권장되는 거 같더군요....

tmddjs210 2년 전 0

그렇군요 답변 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

자바 89% 시간초과 원인 좀 알려주시면 감사하겠습니다.

tmddjs210 3년 전 0

cds06126 2년 전 1

tmddjs210 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말