백준 18111번: 마인크래프트

문제

https://www.acmicpc.net/problem/18111

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class 마인크래프트 {
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int[] nmb = convertStringArrayToIntegerArray(br.readLine().split(" "));

            int n = nmb[0];
            int m = nmb[1];

            int[][] ground = initGround(br, n, m);
            int[] minAndMax = getMinAndMax(ground);

            int[] timeAndHigh = getMinimumConstructionTime(ground, nmb[2], minAndMax[0], minAndMax[1]);

            System.out.println(timeAndHigh[0] + " " + timeAndHigh[1]);
        }
    }

    private static int[] convertStringArrayToIntegerArray(String[] args) {
        int[] array = new int[args.length];
        int i = 0;
        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    private static int[][] initGround(BufferedReader br, int n, int m) throws IOException {
        int[][] ground = new int[n][m];
        for (int i = 0; i < n; i++) {
            ground[i] = convertStringArrayToIntegerArray(br.readLine().split(" "));
        }

        return ground;
    }

    private static int[] getMinAndMax(int[][] ground) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int[] i : ground) {
            for (int j : i) {
                min = min > j ? j : min;
                max = max < j ? j : max;
            }
        }

        return new int[] {min, max};
    }

    private static int[] getMinimumConstructionTime(int[][] ground, int inventory, int min, int max) {
        int answerTime = Integer.MAX_VALUE;
        int answerHigh = 0;

        for (int currentHigh = min; currentHigh <= max; currentHigh++) {
            int up = 0;
            int down = 0;

            for (int i = 0; i < ground.length; i++) {
                for (int j = 0; j < ground[0].length; j++) {
                    int high = ground[i][j] - currentHigh;

                    if (high > 0) {
                        down += high;
                    } else if (high < 0) {
                        up -= high;
                    }
                }
            }

            if (down + inventory >= up) {
                int time = (down * 2) + up;

                if (answerTime >= time) {
                    answerTime = time;
                    answerHigh = currentHigh;
                }
            }
        }

        return new int[]{answerTime, answerHigh};
    }
}

흐름

  1. n * m 크기의 2차원 배열을 만들어서 저장한다.
  2. 땅 높이를 저장한 2차원 배열을 돌면서 가장 작은 높이와 가장 큰 높이를 구한다.
  3. 우선, 가장 낮은 높이부터 가장 높은 높이 까지 반복하면서
  4. 3번에 해당하는 높이를 기준으로 2차원 배열을 2중 루프 돌면서 모든 땅에서 현재 땅 높이를 뺀다. (int high = ground[i][j] - currentHigh;)
  5. 그 높이가 0보다 크면 기준이 되는 땅보다 높은 것 이므로 땅을 깎아서 기준이 되는 높이와 맞추기 위해 down 변수에 높이를 더한다.
  6. 반대로 0 보다 작으면 기준이 되는 땅 보다 낮은 것이므로 땅을 높여서 기준이 되는 높이와 맞추기 위해 up 변수에 높이를 더해야 하는데 high가 0보다 작으면 - 이므로 up에 높이를 - 해서 더한다.
  7. 그렇게 2차원 배열을 전부 반복했으면 땅을 깎으면서 구한 블록과 원래 인벤토리에 있던 블록의 갯수가 쌓아야되는 블록의 갯수보다 크거나 같아야 높이를 맞출 수 있으므로 크거나 같은지 비교해서
  8. 땅을 깎는건 2초가 걸리므로 down * 2 한 값에 쌓아야 되는 높이 만큼 더한다.
  9. 그렇게 구한 걸리는 시간이 이전에 구한 최소 시간 보다 작으면 최소 시간을 지금 구한 time으로 변경하고
  10. 걸리는 시간이 같은 경우엔 가장 높은 높이로 구해야 하므로
  11. 높이도 현재 높이로 바꿔준다.
    • 높이는 제일 작은 높이부터 제일 큰 높이로 순차적으로 올라가고 있으므로 나중에 구한 높이가 이전에 구한 높이 보다 무조건 높다.
  12. 끝.

결과

결과

P.S BFS로 시도했던 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
package algorithm.baekjoon.class2.bruteforce;

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

public class 마인크래프트 {
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int[] nmb = convertStringArrayToIntegerArray(br.readLine().split(" "));

            int n = nmb[0];
            int m = nmb[1];

            int[][] ground = initGround(br, n, m);
            boolean[][] isPassed = new boolean[n][m];

            List<Block> blockList = getBlockList(n, m, ground, isPassed);

            int[] timeAndHigh = getMinimumConstructionTime(blockList, nmb[2]);

            System.out.println(timeAndHigh[0] + " " + timeAndHigh[1]);
        }
    }

    private static int[] convertStringArrayToIntegerArray(String[] args) {
        int[] array = new int[args.length];
        int i = 0;
        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    private static int[][] initGround(BufferedReader br, int n, int m) throws IOException {
        int[][] ground = new int[n][m];
        for (int i = 0; i < n; i++) {
            ground[i]= convertStringArrayToIntegerArray(br.readLine().split(" "));
        }

        return ground;
    }

    private static List<Block> getBlockList(int n, int m, int[][] ground, boolean[][] isPassed) {
        List<Block> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (isPassed[i][j]) {
                    continue;
                }

                int count = breadthFirstSearch(i, j, ground, isPassed);

                list.add(new Block(ground[i][j], count));
            }
        }

        return list;
    }

    private static int breadthFirstSearch(int x, int y, int[][] picture, boolean[][] isPassed) {
        final int[] xAround = new int[]{1, -1, 0, 0};
        final int[] yAround = new int[]{0, 0, 1, -1};

        int areaRange = 1;

        Queue<Position> queue = new LinkedList<>();

        setPassedArea(isPassed, queue, x, y);

        while (!queue.isEmpty()) {
            Position currentPosition = queue.poll();

            for (int i = 0; i < xAround.length; i++) {
                int moveX = xAround[i] + currentPosition.x;
                int moveY = yAround[i] + currentPosition.y;

                if (!isSameAreaValidation(moveX, moveY, picture, isPassed, currentPosition)) {
                    continue;
                }

                setPassedArea(isPassed, queue, moveX, moveY);
                ++areaRange;
            }
        }

        return areaRange;
    }

    private static void setPassedArea(boolean[][] isPassed, Queue<Position> queue, int x, int y) {
        isPassed[x][y] = true;
        queue.offer(new Position(x, y));
    }

    private static boolean isSameAreaValidation(int moveX, int moveY, int[][] picture, boolean[][] isPassed, Position currentPosition) {
        if (isOutOfPicture(moveX, moveY, picture)) {
            return false;
        }

        if (isPassed[moveX][moveY]) {
            return false;
        }

        if (picture[currentPosition.x][currentPosition.y] != picture[moveX][moveY]) {
            return false;
        }

        return true;
    }

    private static boolean isOutOfPicture(int moveX, int moveY, int[][] picture) {
        if (moveX < 0 || moveY < 0) {
            return true;
        }

        if (picture.length <= moveX || picture[0].length <= moveY) {
            return true;
        }

        return false;
    }

    private static int[] getMinimumConstructionTime(List<Block> blockList, int inventory) {
        int answerTime = Integer.MAX_VALUE;
        int answerHigh = 0;

        for (Block currentBlock : blockList) {
            int currentHigh = currentBlock.high;

            int up = 0;
            int down = 0;

            for (Block loopBlock : blockList) {
                int loopHigh = loopBlock.high;
                int loopCount = loopBlock.count;

                if (currentHigh > loopHigh) {
                    up += (currentHigh - loopHigh) * loopCount;
                } else if (currentHigh < loopHigh) {
                    down += (loopHigh - currentHigh) * loopCount;
                }
            }

            if (down + inventory >= up) {
                int time = (down * 2) + up;

                if (answerTime > time) {
                    answerTime = time;
                    answerHigh = currentBlock.high;
                }
            }
        }

        return new int[]{answerTime, answerHigh};
    }

    static class Block {
        private Integer high;
        private Integer count;

        public Block(Integer high, Integer count) {
            this.high = high;
            this.count = count;
        }
    }

    static class Position {
        private int x;
        private int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
  • BFS로 높이 별 갯수를 구한 후 높이 별로 sorting 하여 처리 하려고 했는데 시간 초과로 실패

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job