Algorithm-practice/src/_2020_KAKAO_BLIND_RECRUITMENT/P5/Main.java at master · Seogeurim/Algorithm-practice · GitHub

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
package _2020_KAKAO_BLIND_RECRUITMENT.P5;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        Solution sol = new Solution();

        int n = 5;
        int[][] build_frame = {{1,0,0,1},{1,1,1,1},{2,1,0,1},{2,2,1,1},{5,0,0,1},{5,1,0,1},{4,2,1,1},{3,2,1,1}};

        System.out.println(Arrays.deepToString(sol.solution(n, build_frame)));

        int m = 5;
        int[][] build_frame2 = {{0,0,0,1},{2,0,0,1},{4,0,0,1},{0,1,1,1},{1,1,1,1},{2,1,1,1},{3,1,1,1},
        {2,0,0,0},{1,1,1,0},{2,2,0,1}, {0,0,0,0}};

        System.out.println(Arrays.deepToString(sol.solution(m, build_frame2)));
    }
}

class Solution {

    static boolean[][] col;
    static boolean[][] row;
    static int max_idx;
    static int count;

    public int[][] solution(int n, int[][] build_frame) {
        int[][] answer;

        col = new boolean[n+1][n+1];
        row = new boolean[n+1][n+1];
        max_idx = n;
        count = 0;

        for (int[] build : build_frame) {
            int x = build[0];
            int y = build[1];
            int a = build[2];
            int b = build[3];
            if (b == 1) {
                if (a == 0) addColumn(x, y);
                else addRow(x, y);
            } else {
                remove(x, y, a);
            }
        }

        answer = new int[count][3];
        int idx = 0;

        for (int i = 0; i < n+1; i++) {
            for (int j = 0; j < n+1; j++) {
                if (col[i][j]) answer[idx++] = new int[]{i, j, 0};
                if (row[i][j]) answer[idx++] = new int[]{i, j, 1};
            }
        }

        return answer;
    }

    static boolean canGo(int idx) {
        return idx >= 0 && idx <= max_idx;
    }

    static boolean isValidCol(int x, int y){
        return y == 0 ||
                (canGo(x-1) && row[x-1][y]) ||
                row[x][y] ||
                (canGo(y-1) && col[x][y-1]);
    }

    static boolean isValidRow(int x, int y){
        return (canGo(y-1) && col[x][y-1]) ||
                (canGo(x+1) && canGo(y-1) && col[x+1][y-1]) ||
                (canGo(x-1) && canGo(x+1) && row[x-1][y] && row[x+1][y]);
    }

    static void addColumn(int x, int y){
        if (isValidCol(x, y)) {
            col[x][y] = true;
            count ++;
        }
    }

    static void addRow(int x, int y){
        if (isValidRow(x, y)) {
            row[x][y] = true;
            count ++;
        }
    }

    static void remove(int x, int y, int type){
        if (type == 0) col[x][y] = false;
        else row[x][y] = false;
        count --;

        for (int i = 0; i < max_idx+1; i++) {
            for (int j = 0; j < max_idx+1; j++) {
                if (col[i][j] && !isValidCol(i, j)) {
                    if (type == 0) col[x][y] = true;
                    else row[x][y] = true;
                    count ++;
                    return;
                }
                if (row[i][j] && !isValidRow(i, j)) {
                    if (type == 0) col[x][y] = true;
                    else row[x][y] = true;
                    count ++;
                    return;
                }
            }
        }
    }
}