글 읽기 - 시간초과 좀 해결 할 수 있을까요?

wow1514 8년 전 0

check변수를 통해 중복된 값이 들어올때마다 1씩 증가시켜주고

check 값이 N*M값을 넘으면 싸이클로 인식하게 했습니다.

시간초과가.. 뜨네요 ㅠㅠ

import java.util.Scanner;
 
public class Main{
    static int N,M;
    static int[][] arr;
    static int max;
    static boolean flag;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N][M];
        int[][] visited = new int[N][M];
        max = 0;
        flag = false;
        for(int i = 0; i < N; i++){
            String buf = sc.next();
            for(int j = 0; j < M; j++){
                int c = buf.charAt(j);
                if(c == 'H')
                    arr[i][j] = -1;
                else
                    arr[i][j] = (int)c - 48;
            }
        }
        DFS(visited,0,0,0);
        if(!flag)
            System.out.println(max+1);
        else
            System.out.println(-1);
        sc.close();
    }
    static void DFS(int[][] visited, int x, int y, int check){
        if(flag)
            return;
        int move = arr[x][y];
         
        if(check >= N*M && !flag){
            flag = true;
            return;
        }
 
        //위
        if(x-move >= 0 && arr[x-move][y] != -1 && visited[x-move][y] == 0){
            visited[x-move][y] = visited[x][y] + 1;
            if(max < visited[x][y])
                max = visited[x][y];
            DFS(visited,x-move,y,check);
        }
        //게임을 끝내야 할때
        else if(x-move < 0 || arr[x-move][y] == -1){
            if(max < visited[x][y])
                max = visited[x][y];
            //return;
        }
        else if(visited[x-move][y] != 0){
            DFS(visited,x-move,y,++check);
        }
        //아래
        if(x+move < N && arr[x+move][y] != -1 && visited[x+move][y] == 0){
            visited[x+move][y] = visited[x][y] + 1;
            if(max < visited[x][y])
                max = visited[x][y];
            DFS(visited,x+move,y,check);
        }
        //게임을 끝내야 할때
        else if(x+move >= N || arr[x+move][y] == -1){
            if(max < visited[x][y])
                max = visited[x][y];
            //return;
        }
        else if(visited[x+move][y] != 0){
            DFS(visited,x+move,y,++check);
        }
        //왼
        if(y-move >= 0 && arr[x][y-move] != -1 && visited[x][y-move] == 0){
            visited[x][y-move] = visited[x][y] + 1;
            if(max < visited[x][y])
                max = visited[x][y];
            DFS(visited,x,y-move,check);
        }
        //게임을 끝내야 할때
        else if(y-move < 0 || arr[x][y-move] == -1){
            if(max < visited[x][y])
                max = visited[x][y];
            //return;
        }
        else if(visited[x][y-move] != 0){
            check++;
            DFS(visited,x,y-move,++check);
        }
        //오른쪽
        if(y+move < M && arr[x][y+move] != -1 && visited[x][y+move] == 0){
            visited[x][y+move] = visited[x][y] + 1;
            if(max < visited[x][y])
                max = visited[x][y];
            DFS(visited,x,y+move,check);
        }
        //게임을 끝내야 할때
        else if(y+move >= M || arr[x][y+move] == -1){
            if(max < visited[x][y])
                max = visited[x][y];
            //return;
        }
        else if(visited[x][y+move] != 0){
            DFS(visited,x,y+move,++check);
        }
    }
}

badcandy 7년 전 0

중복되는 부분이 있기 때문에 DP를 써서 풀어야 해요.

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

문제

문제

출처

ICPC

시간초과 좀 해결 할 수 있을까요?

wow1514 8년 전 0

badcandy 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말