글 읽기 - [Java] 시간 줄일 힌트 부탁드려요

nahwasa 2년 전 0

1. 높이순서로 정렬 : order[]

2. h-d가 0 미만일 경우 계산해볼 이유가 없으므로, h-d가 0이상일때에 대해 높은 높이부터 빼내서 bfs 돌림.

3. 이 때, h-d 초과인 높이에 대해서만 bfs를 돌림. 돌리다가 이미 방문했던 곳 (visited[][] == true)을 만나면 거긴 정상이 아님.

curVisited랑 visited로 분리해둔 이유는, curVisited가 false이고 visited가 true라면 그 이전 order에서 방문한 곳이란걸 판단하기 위해서 입니다.

---

그럼 예상으로는 어쨌든 bfs 최대로 돌아도 500x500번 돌테니 대충 '2'의 경우에 해당하지 않는 최악의 경우라도 bfs는 최대 25만번이고, tc가 100번이고 하니 대강 시간내에 될 것 같았는데.. 시간초과가 납니다.

혹시 시간을 더 줄일 만한 힌트좀 부탁드려도 될까요?

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

class Pos {
    int r, c;
    public Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    private static final int[] dr = {0, 0, 1, -1};
    private static final int[] dc = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder result = new StringBuilder();

        while (tc-->0) {
            // for each case
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            int[][] height = new int[r][c];
            boolean[][] visited = new boolean[r][c];
            Pos[] order = new Pos[r*c];

            for (int i = 0; i < r; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < c; j++) {
                    height[i][j] = Integer.parseInt(st.nextToken());
                    order[i*c+j] = new Pos(i, j);
                }
            }

            // solve
            Arrays.sort(order, (a, b) -> height[b.r][b.c] - height[a.r][a.c]);

            int eachCaseCnt = 0;
            for (int it = 0; it < r*c; it++) {
                Pos cur = order[it];
                int startHeight = height[cur.r][cur.c];
                int hmd = startHeight - d; // hmd ; h-d
                if (hmd < 0)   // pass impossible points
                    break;
                if (visited[cur.r][cur.c])
                    continue;

                int cnt = 0;

                // bfs
                Queue<Pos> q = new LinkedList<>();
                q.add(cur);
                visited[cur.r][cur.c] = true;
                boolean[][] curVisited = new boolean[r][c];
                curVisited[cur.r][cur.c] = true;

                while (!q.isEmpty()) {
                    Pos pos = q.poll();
                    if (height[pos.r][pos.c] == startHeight)
                        cnt++;

                    for (int i = 0; i < 4; i++) {
                        int nr = pos.r + dr[i];
                        int nc = pos.c + dc[i];
                        if (nr<0 || nr>=r || nc<0 || nc>=c || curVisited[nr][nc] || height[nr][nc] <= hmd)
                            continue;
                        if (visited[nr][nc]) {
                            cnt = 0;
                            break;
                        }
                        curVisited[nr][nc] = true;
                        visited[nr][nc] = true;
                        q.add(new Pos(nr, nc));
                    }
                    if (cnt == 0)   // not top
                        break;
                }
                eachCaseCnt += cnt;
            }
            result.append(eachCaseCnt).append('\n');
        }
        System.out.println(result);
    }
}

nahwasa 2년 전 0

로직적으론 더이상 생각이 안나서.. 한땀한땀 시간을 깎아서 겨우 턱걸이로 통과했네요 ㅠㅠ

이제 다른 고수분들 코드보고 어케하셨나좀 봐야할덧

nahwasa 2년 전 0

는 시간도 해결함. 편-안

로직상 문제보다는 세세하게 뭘 쓰냐에 따라 시간이 갈렸었군요.

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

문제

문제

출처

ICPC

[Java] 시간 줄일 힌트 부탁드려요

nahwasa 2년 전 0

nahwasa 2년 전 0

nahwasa 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말