글 읽기 - [Java] 최적화 질문입니다

zzz8838 4년 전 0

시간이 최소로 걸린 분 소스코드를 보면 DFS로 푸셨는데, 저는 BFS를 이용해서 바이러스 매핑을 처리했습니다.

BFS가 DFS보다 효율적이라 생각했는데 메모리가 거의 10배(119572kb), 시간은 4배(400ms) 정도가 걸립니다.

어떤 차이에 의해서 메모리와 시간이 이렇게 차이나는지 모르겠습니다.

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

public class Main {
    private static boolean[][] infected;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        int height = Integer.parseInt(input[0]);
        int width = Integer.parseInt(input[1]);
        map = new int[height][width];
        infected = new boolean[height][width];

        for (int i = 0; i < height; i++) {
            input = reader.readLine().split(" ");
            for (int j = 0; j < width; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        int result = 0;
        int mul = height * width;
        for (int i = 0; i < mul - 2; i++) {
            if (map[i / width][i % width] != 0)
                continue;
            map[i / width][i % width] = 1;

            for (int j = i + 1; j < mul - 1; j++) {
                if (map[j / width][j % width] != 0)
                    continue;
                map[j / width][j % width] = 1;

                for (int k = j + 1; k < mul; k++) {
                    if (map[k / width][k % width] != 0)
                        continue;
                    map[k / width][k % width] = 1;
                    spreadVirus();
                    result = Math.max(countSafety(), result);
                    map[k / width][k % width] = 0;
                }
                map[j / width][j % width] = 0;
            }
            map[i / width][i % width] = 0;
        }

        System.out.println(result);
    }

    private static void spreadVirus() {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == 2) {
                    spreadBFS(i, j);
                }
            }
        }
    }

    private static void spreadBFS(int y, int x) {
        Queue<Integer> x_que = new LinkedList<>();
        Queue<Integer> y_que = new LinkedList<>();
        x_que.offer(x);
        y_que.offer(y);

        while (!x_que.isEmpty()) {
            x = x_que.poll();
            y = y_que.poll();

            if (x - 1 >= 0 && map[y][x - 1] == 0 && !infected[y][x - 1]) {
                x_que.offer(x - 1);
                y_que.offer(y);
                infected[y][x - 1] = true;
            }
            if (x + 1 < map[0].length && map[y][x + 1] == 0 && !infected[y][x + 1]) {
                x_que.offer(x + 1);
                y_que.offer(y);
                infected[y][x + 1] = true;
            }
            if (y - 1 >= 0 && map[y - 1][x] == 0 && !infected[y - 1][x]) {
                x_que.offer(x);
                y_que.offer(y - 1);
                infected[y - 1][x] = true;
            }
            if (y + 1 < map.length && map[y + 1][x] == 0 && !infected[y + 1][x]) {
                x_que.offer(x);
                y_que.offer(y + 1);
                infected[y + 1][x] = true;
            }
        }
    }

    private static int countSafety() {
        int count = 0;
        for (int i = 0; i < infected.length; i++) {
            for (int j = 0; j < infected[0].length; j++)
                if (!infected[i][j] && map[i][j] == 0) count++;
                else infected[i][j] = false;
        }
        return count;
    }

}

seico75 4년 전 0

LinkedList 를 ArrayDeque 로 바꾸면 메모리와 속도가 조금 개선이 되네여. (채점번호 : 16700206)

DFS 로 해도 획기적인 개선은 없는 것 같은데.. (채점번호 : 1197379)

zzz8838 4년 전 0

라이브러리에 따라 많은 차이가 나는군요!

그래도 제일 빠른 코드와 120ms 차이가 나는데 자료구조와 라이브러리에 대한 공부를 더 해야겠습니다.

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

문제

문제

출처

ICPC

[Java] 최적화 질문입니다

zzz8838 4년 전 0

seico75 4년 전 0

zzz8838 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말