글 읽기 - 계속 시간 초과가 나오네요...ㅠ

ac9831 6년 전 0

어디가 문제 있을까요..ㅠ

한번 봐주시고 고수분들의 도움이 필요 합니다!

import java.util.*;

// 기능별로 File을 만들기에는 양이 적어서 일반 코딩 시험처럼 한 Class안에 전부 구현했습니다.
// 만약 실무에서 한다면 파일이 3~4개정도 될 것이며 비슷한 기능끼리 묶어서 작업했을 것입니다.
public class Main {

    static char[][] map;
    static int[][] mapVal;
    static int n;
    static int[][] visitmap;
    static int[] dy = { -1, 0, 0, 1, -1, -1, 1, 1};
    static int[] dx = { 0, -1, 1, 0, -1, 1, -1, 1};

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        map = new char[n][n];

        mapVal = new int[n][n];
        List<Integer> sortVal = new ArrayList<Integer>();

        int startX = 0;
        int startY = 0;
        int KCount = 0;

        for(int i=0;i<n;i++){
            String tmp = sc.next();
            for(int j=0;j<n;j++){
                map[i][j] = tmp.charAt(j);
                if(tmp.charAt(j) == 'P'){
                    startX = j;
                    startY = i;
                }
                if(tmp.charAt(j) == 'K'){
                    KCount++;
                }
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                mapVal[i][j] = sc.nextInt();
                sortVal.add(mapVal[i][j]);
            }
        }

        Collections.sort(sortVal);

        List<Integer> val = new ArrayList<Integer>();

        for(int i=0;i<sortVal.size()-1;i++){
            if(sortVal.get(i) != sortVal.get(i+1)){
                val.add(sortVal.get(i));
            }
        }
        if(val.get(val.size()-1) != sortVal.get(sortVal.size()-1)){
            val.add(sortVal.get(sortVal.size()-1));
        }

        int ans = Integer.MAX_VALUE;
        int s = 0, e =0;
        while(e<val.size()){
            visitmap = new int[n][n];

            visitmap[startY][startX] = 1;

            if(DFS(val.get(s), val.get(e),startX,startY) == KCount){
                if(val.get(e) - val.get(s) < ans){
                    ans = val.get(e) - val.get(s);
                    s++;
                }
            }else{
                e++;
            }
        }
        System.out.println(ans);

    }


    public static int DFS(int min, int max, int X, int Y) {
        int ret = 0;

        if(mapVal[Y][X] > max || mapVal[Y][X] < min) return 0;
        if(map[Y][X] == 'K'){
            ret = 1;
        }

        for(int i=0;i<8;i++){
            int nextX = X + dx[i];
            int nextY = Y + dy[i];
            if(nextY >= 0 && nextY < n && nextX >= 0 && nextX < n){
                if(visitmap[nextY][nextX] == 0){
                    visitmap[nextY][nextX] = 1;
                    ret += DFS(min, max, nextX, nextY);
                }
            }
        }

        return ret;

    }
}

zlzmsrhak 6년 전 0

반례입니다. 72번째 줄이 if문 바깥으로 나와야 할 것 같습니다.

3
K.P
...
...
5 3 5
5 9 5
5 3 5

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

문제

문제

출처

ICPC

계속 시간 초과가 나오네요...ㅠ

ac9831 6년 전 0

zlzmsrhak 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말