[카카오 2020 공채] 기둥과 보

2020년 카카오 공채 기둥과 보 해설입니다

---

2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치하는 문제입니다. 특정 알고리즘 지식을 요구하는 문제는 아니고 기둥과 보를 설치할 수 있는 조건을 잘 이해하고 적용하면 해결할 수 있습니다.

기둥과 보를 설치할 수 있는 조건은 아래와 같습니다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

위 조건을 (x, y, a)의 튜플로 나타내 보겠습니다.

for x, y, a in installed:
    if a == 0: # 기둥을 설치할 경우
        if y == 0 or # 바닥에 기둥을 설치한다
            (x, y - 1, 0) in installed or # 바로 아래 기둥이 설치 되어 있다
            (x - 1, y, 1) in installed or
            (x, y, 1) in installed: # 한 쪽 끝에 보가 설치 되어있다
            continue
        return False # 조건 만족 X

    else: # 보를 설치할 경우
        if (x, y - 1, 0) in installed or 
            (x + 1, y - 1, 0) in installed or  # 한쪽 끝 부분이 기둥 위에 있다
            ((x - 1, y, 1) in installed and (x + 1, y, 1) in installed): # 양쪽 끝 부분이 다른 보와 연결되어 있다
            continue
        return False # 조건 만족 X

    return True

기둥을 설치하는 경우 (x - 1, y, 1) in installed or (x, y, 1) in installed 코드가 이해되지 않을 수 있습니다.

이는 보를 (n, m)에 설치하는 경우 (n, m) ~ (n+1, m)까지 설치되기 때문입니다. 다시 말하면, (n-1, m)에 보를 설치하면 (n-1, m) ~ (n, m) 구간까지 보가 설치됩니다.

Java

import java.util.*;
class Solution {
    static class CustomComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] s1, int[] s2) {
            if (s1[0] != s2[0])
                return s1[0] - s2[0];

            if (s1[1] != s2[1])
                return s1[1] - s2[1];

            return s1[2] - s2[2];
        }
    }

    static class Structure {
        int x, y, type;

        Structure(int x, int y, int type) {
            this.x = x;
            this.y = y;
            this.type = type;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Structure) {
                Structure other = (Structure) obj;
                return x == other.x && y == other.y && type == other.type;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            return "x: " + x + " y: " + y + " type: " + type;
        }
    }
    Set<Structure> frame = new HashSet<>();
    public int[][] solution(int n, int[][] build_frame) {

        for (int[] cmd : build_frame) {
            Structure st = new Structure(cmd[0], cmd[1], cmd[2]);
            if (cmd[3] == 0) { // delete
                frame.remove(st);

                if (isNotValid())
                    frame.add(st);

            } else {
                frame.add(st);

                if (isNotValid())
                    frame.remove(st);
            }
        }
        Iterator<Structure> iter = frame.iterator();
        int[][] answer = new int[frame.size()][3];
        int idx = 0;
        while(iter.hasNext()) {
            Structure st = iter.next();
            answer[idx++] = new int[] {st.x, st.y, st.type};
        }

        Arrays.sort(answer, new CustomComparator());

        return answer;
    }



    private boolean isNotValid() {
        Iterator<Structure> iter = frame.iterator();

        while(iter.hasNext()) {
            Structure st = iter.next();

            if (st.type == 0) { // 기둥
                if (st.y == 0 || frame.contains(new Structure(st.x, st.y, 1)) 
                    || frame.contains(new Structure(st.x - 1, st.y, 1)) || frame.contains(new Structure(st.x, st.y - 1, 0))){
                    continue;
                }
                return true;
            } else { // 보
                if (frame.contains(new Structure(st.x, st.y - 1, 0)) || frame.contains(new Structure(st.x + 1, st.y - 1, 0))
                   || (frame.contains(new Structure(st.x - 1, st.y, 1)) && frame.contains(new Structure(st.x + 1, st.y, 1))))
                    continue;
                return true;
            }
        }
        return false;
    }
}

Python

def solution(n, build_frame):
    answer = [[]]
    installed = set()

    for x, y, a, b in build_frame:
        if b == 0: # delete
            installed.remove((x, y, a))

            if is_not_valid(installed):
                installed.add((x, y, a))

        else:
            installed.add((x, y, a))

            if is_not_valid(installed):
                installed.remove((x, y, a))

    return list(sorted(installed, key = lambda x: (x[0], x[1], x[2])))

def is_not_valid(installed):
    for x, y, a in installed:
        if a == 0: # 기둥
            if y == 0 or (x, y - 1, 0) in installed or (x, y, 1) in installed\
                or (x - 1, y, 1) in installed:
                    continue

            return True
        else:
            if (x, y - 1, 0) in installed or (x + 1, y - 1, 0) in installed\
                or ((x - 1, y, 1) in installed and (x + 1, y, 1) in installed):
                    continue

            return True
    return False