글 읽기 - 시간 복잡도가 궁금합니다.(자바)

wooserk 3년 전 0

제 코드로 정답을 맞췄을 때 시간이 700ms정도 나오는데, 다른 분들의 코드를 보면 물론 저랑 비슷한 분들도 많지만 250~350ms정도 나오는 코드들이 종종 있기에 몇몇 코드를 살펴봤는데, 어디서 차이가 나는지 잘 모르겠습니다.

대충 예상하고 거리 배열을 2차원으로 선언하는 등의 나름 수정을 해서 제출해봤는데 오히려 더 크게 나올 때도 많아서 혼란스럽습니다..

어디서 차이가 나는 건지 알려주시면 감사하겠습니다!

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

public class Q4991
{
    static int w;
    static int h;
    static char[][] ary = new char[21][21];
    static int[][][] dist = new int[21][21][21];
    static ArrayList<int[]> dust;
    static int dustNum;
    static boolean[] dustCheck;
    static int min;

    public static void foo(int index, int prev, int sum)
    {
        if(index == dustNum)
        {
            if(sum < min)
                min = sum;

            return;
        }

        for(int i=0; i<dustNum; i++)
        {
            if(dustCheck[i])
                continue;

            dustCheck[i] = true;

            int[] cur = dust.get(i);
            foo(index+1, i, sum + dist[prev+1][cur[0]][cur[1]]);

            dustCheck[i] = false;
        }
    }

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

        StringBuilder sb = new StringBuilder();
        while(true)
        {
            // 최솟값 초기화
            min = Integer.MAX_VALUE;

            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            if(w == 0 && h == 0)
                break;

            dust = new ArrayList<>();
            dustCheck = new boolean[10];

            int sRow = 0;
            int sCol = 0;

            for (int i = 0; i < h; i++)
            {
                String str = br.readLine();

                for (int j = 0; j < w; j++)
                {
                    ary[i][j] = str.charAt(j);
                    // 시작 지점
                    if (ary[i][j] == 'o')
                    {
                        sRow = i;
                        sCol = j;
                    }
                    // 먼지
                    else if(ary[i][j] == '*')
                        dust.add(new int[]{i, j});
                }
            }

            dustNum = dust.size();

            // k = 0 : 시작 지점에서의 거리, k = 1 ~ dustNum : 먼지에서 먼지까지 거리
            for(int k=0; k<=dustNum; k++)
            {
                for(int i=0; i<h; i++)
                {
                    for(int j=0; j<w; j++)
                        dist[k][i][j] = -1;
                }
            }

            int[] dr = {-1, 0, 0, 1};
            int[] dc = {0, -1, 1, 0};

            Queue<int[]> queue = new LinkedList<>();

            for(int k=0; k<=dustNum; k++)
            {
                // 먼지 위치에서 시작
                if(k != 0)
                {
                    sRow = dust.get(k-1)[0];
                    sCol = dust.get(k-1)[1];
                }

                // 시작 지점 초기화
                dist[k][sRow][sCol] = 0;

                queue.add(new int[]{sRow, sCol});

                while (!queue.isEmpty())
                {
                    int[] tmp = queue.poll();

                    for (int i = 0; i < 4; i++)
                    {
                        int newRow = tmp[0] + dr[i];
                        if (newRow < 0 || newRow >= h)
                            continue;

                        int newCol = tmp[1] + dc[i];
                        if (newCol < 0 || newCol >= w)
                            continue;

                        // 이미 들렀으면 다음 방향 검사 || 벽이면 다음 방향 검사
                        if (dist[k][newRow][newCol] != -1 || ary[newRow][newCol] == 'x')
                            continue;

                        queue.add(new int[]{newRow, newCol});
                        dist[k][newRow][newCol] = dist[k][tmp[0]][tmp[1]] + 1;
                    }
                }
            }

            // 방문할 수 없는 더러운 칸이 있는지 확인
            for(int i=0; i<dustNum; i++)
            {
                int[] cur = dust.get(i);
                if(dist[0][cur[0]][cur[1]] == -1)
                    min = -1;
            }

            if(min != -1)
            {
                for (int i = 0; i < dustNum; i++)
                {
                    dustCheck[i] = true;

                    int[] tmp = dust.get(i);
                    foo(1, i, dist[0][tmp[0]][tmp[1]]);

                    dustCheck[i] = false;
                }
            }

            sb.append(min).append('\n');
        }

        System.out.print(sb.toString());
    }
}

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

문제

문제

출처

ICPC

시간 복잡도가 궁금합니다.(자바)

wooserk 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말