글 읽기 - 97%에서 시간 초과나는데 왜 그런지 모르겠습니다.

nodays 2년 전 0

97%에서 시간 초과나는데 왜 그런지 모르겠습니다. 도와주세요

package BOJ.BFS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_16930 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int k = stoi.apply(st.nextToken());
        char[][] map = new char[n][m];
        for(int i = 0 ; i < n ; i++){
            String command = br.readLine();
            for(int j = 0 ; j < m ; j++){
                map[i][j] = command.charAt(j);
            }
        }
        st = new StringTokenizer(br.readLine()," ");
        int startY = stoi.apply(st.nextToken()) - 1;
        int startX = stoi.apply(st.nextToken()) - 1;
        int endY = stoi.apply(st.nextToken()) - 1;
        int endX = stoi.apply(st.nextToken()) - 1;
        System.out.println(bfs(map,n,m,k,startY,startX,endY,endX));
    }

    private static  int bfs(char[][] map, int n ,int m , int k, int startY, int startX, int endY, int endX) {
        final int dy[] = {-1,0,1,0};
        final int dx[] = {0,1,0,-1};
        Queue<int[]> q = new LinkedList< >();
        boolean[][] visited = new boolean[n][m];
        q.offer(new int[] {startY,startX});
        visited[startY][startX] = true;
        int time = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int[] now = q.poll();
                if(now[0] == endY && now[1] == endX){
                    return time;
                }
                for(int i = 0 ; i < 4 ; i++){
                    int ny = now[0];
                    int nx = now[1];
                    for(int j = 1 ; j <= k ; j++){
                        ny += dy[i];
                        nx += dx[i];
                        if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[ny][nx] == '.'){
                            if(!visited[ny][nx]){
                                visited[ny][nx] = true;
                                q.offer(new int[]{ny,nx});
                            }
                        }else{
                            break;
                        }
                    }
                }
            }
            time++;
        }
        return -1;
    }
}

ajongs 1년 전 11

글쓴이님은 해결하신 것 같지만 97%에서 시간초과로 어려움을 겪으시는 분들을 위해 댓글을 남깁니다.

먼저 큰 힌트는 우리는 visited 배열에 방문하는 시점의 시간을 저장해야합니다. 다음 칸이 나보다 더 빠르거나 같은 시간에 방문 되었다면 그방향은 조사할 필요가 없습니다.

저도 한참을 고민했는데 아래의 좌표를 봐주십시오.

N = 8, M = 9, K = 4 라고 가정하고

(1,1)에서 처음으로 bfs를 돌렸을 때 visited 배열이 아래와 같을 것입니다.

0 1 1 10 0 0 0 0

1 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

여기서 중요한 점은 (2,1), (2, 2) 는 아래방향은 조사할 필요가 없고, (1,2), (1,3) 은 오른쪽 방향을 조사할 필요가 없다는 것입니다.

예를 들면 (2,1) 은 최대 (1 + k) = 5 번째 아래방향 까지 조사합니다. (2,2) 는 최대 (2 + k) = 6 번째 아래방향까지 조사합니다.

하지만 (2,3) 은 (3 + k) = 7번째 방향까지 조사합니다. 따라서 (2,3)만 아래방향을 조사하면 (2,1) (2,2)가 조사해야 하는 방향까지 조사가 가능하다는 것이죠.

(1,2) (1,3)도 마찬가지로 오른쪽 방향 조사는 (1,4) 가 혼자 맡아서 하면됩니다.

따라서, 다음 칸이 자신보다 같거나 작은 시간에 visited 했다면 break 하고 다음 칸에게 해당 방향 조사를 위임해주면 해결할 수 있습니다.

말이 조금 어려워서 이해가 가실지는 모르겠으나, 많은 힌트를 드렸다고 생각합니다.

jeen0112 1년 전 1

자신보다 같거나 작은 시간이라고 하셨는데 같은 시간에는 왜 break해야하는지 모르겠습니다. 같은 시간에는 그냥 continue하다가 혹시나 for문에서 더 작은 값을 찾으면 또 갱신할 수 있지 않을까요? 같을 때 break하니까 틀려서 댓글을 남깁니다. 같다를 제거하니 맞네요

luke0985 17일 전 0

힌트덕에 푼 것 같습니다 감사합니다.

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