글 읽기 - 시간초과.. 어디가 문제일까요??

ljy2784437 2년 전 0

안녕하세요.글을 읽어 주셔서 감사합니다.

아래 코드에서 어떤 부분이 시간복잡도에서 치명적일까요..?

제 생각엔 구현 내용에는 문제가 없는데.. 갈피를 못잡고 있어 질문 드립니다.

구현 내용에서도 문제점을 발견하신다면 알려주세요ㅎㅎ..

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

public class Main {

    static int N;
    static int M;
    static int P;

    static int[] canMoves;      // 각 player들이 움직일 수 있는 거리
    static char[][] map;        // map
    static boolean[][] visit;   // visit

    static Queue<Coordinate>[] queues;     // 각 player에 대한 queue
    static int[] players;       //각 player의 이동 거리

    public static void main(String[] args) throws IOException {
        try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {
            inputs(bufferedReader);

            while (true) {
//                매 round를 진행
                if (getRound()) {
                    break;
                }
            }

            StringBuilder answer = getAnswer();
            System.out.println(answer);
        }
    }

    private static boolean getRound() {
        int emptyRound = 0;
        for (int idx = 1; idx <= P; idx++) {
            if (queues[idx].isEmpty()) {
                emptyRound++;

                continue;
            }
//            queue가 비어있지 않으면, bfs 탐색 진행
            bfs(idx);
        }

//        모든 round가 empty이면 탐색을 종료
        return emptyRound == P;
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    private static void bfs(int idx) {
//        idx번째 player가 갈 수 있는 거리만큼
        for (int count = 0; count < canMoves[idx]; count++) {
//            queue[idx].size()만큼 반복을 진행하는 이유는 player별 턴을 갖기위함
            int size = queues[idx].size();
            for (int i = 0; i < size; i++) {
                Coordinate cur = queues[idx].poll();

//                각 위치별로 4방향을 이동시켜 성을 쌓을 수 있는지 검사
                for (int dir = 0; dir < 4; dir++) {
                    int nextX = cur.getX() + dx[dir];
                    int nextY = cur.getY() + dy[dir];

//                    map의 범위가 아니거나 이미 방문했거나 벽인 경우 continue
                    if (!isInMap(nextX, nextY) || visit[nextX][nextY]
                        || map[nextX][nextY] == '#') {
                        continue;
                    }

//                    map의 범위이고 방문하지 않았으며 빈 공간이거나 현재 숫자와 같은 경우
                    if (map[nextX][nextY] == '.' || map[nextX][nextY] - '0' == idx) {
//                        현재 player의 queue에 삽입
                        queues[idx].add(new Coordinate(nextX, nextY));
                        map[nextX][nextY] = map[cur.getX()][cur.getY()];
                        visit[nextX][nextY] = true;
                        players[idx]++;     //player의 크기 증가
                    }
                }
            }
        }
    }

    private static boolean isInMap(int nextX, int nextY) {
        return nextX >= 0 && nextY >= 0 && nextX < N && nextY < M;
    }

//    player들에 대한 출력 조건
    private static StringBuilder getAnswer() {
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i <= P; i++) {
            builder.append(players[i]).append(" ");
        }

        return builder;
    }

    private static void inputs(BufferedReader bufferedReader) throws IOException {
        StringTokenizer inputLine = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(inputLine.nextToken());
        M = Integer.parseInt(inputLine.nextToken());
        P = Integer.parseInt(inputLine.nextToken());

        canMoves = new int[P + 1];
        players = new int[P + 1];
        inputLine = new StringTokenizer(bufferedReader.readLine());
        for (int i = 1; i <= P; i++) {
            canMoves[i] = Integer.parseInt(inputLine.nextToken());
        }

        queues = new Queue[P + 1];
        for (int i = 1; i <= P; i++) {
            queues[i] = new LinkedList<>();
        }

        map = new char[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String rows = bufferedReader.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = rows.charAt(j);

                if (map[i][j] - '0' >= 0 && map[i][j] - '0' <= 9) {
                    queues[map[i][j] - '0'].add(new Coordinate(i, j));
                    players[map[i][j] - '0']++;
                    visit[i][j] = true;
                }
            }
        }
    }

    static class Coordinate {

        private final int x;
        private final int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

}

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

문제

문제

출처

ICPC

시간초과.. 어디가 문제일까요??

ljy2784437 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말