[1일 1알고] 기둥과 보 설치

https://school.programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

 

 

가장 중요하다고 생각되는 지점은 기둥과 보에 대해서 기준을 어떻게 잡을 지 입니다.

 

전체 정사각 격자에서 기둥과 보가 array특정 위치 x, y지점에서 어떻게 존재하고 있는지 기준을 명확히 잡아야 이후 풀이에서도 헷갈리는 점이 없습니다.

 

저는 x, y일 때 (x, y)에서 위로 뻗는 '기둥', (x,y)에서 오른쪽으로 가는 '보' 라고 생각하고 진행했습니다.

---

또한 한 점에서 기둥과 보가 동시에 존재할 수 있기 때문에 해당 상태를 어떻게 표현할지도 정해야합니다.

저는 아래와 같이 enum으로 상태를 정하고 이와 같이 진행함으로서 bitmasking을 활용하기도 좋아졌습니다.

enum wall_state
{
    NOTHING = 0,
    PILLAR = 1,
    BEAM = 2,
    ALL = 3,
};

 

아래는 이번 문제를 해결하기 위해 만든 별도의 메서드입니다.

is_safe는 x, y지점에서 ws 상태라면 현재 안전한 상태인지를 확인합니다.

 

ALL일 때는 둘다 확인할 수 있도록 만드려고 했습니다.

 

flag의 활용을 조금 읽게 힘들게 만든 문제는 있네요 

flag가 false라는 것은 안전하다는 뜻입니다.

bool check(int x, int y, wall_state ws)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;

    return (wall[x][y] & ws) > 0;
}

bool is_safe(int x, int y, wall_state ws)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return true;
    if ((ws & PILLAR) > 0)
    {
        bool flag = true;
        if (y == 0)
            flag = false;
        else if (check(x, y, BEAM) || check(x - 1, y, BEAM)
            || check(x, y - 1, PILLAR))
        {
            flag = false;
        }
        if (flag)
            return false;
    }

    if ((ws & BEAM) > 0)
    {
        bool flag = true;
        if (check(x, y-1, PILLAR) || check(x + 1, y -1, PILLAR)
            || (check(x-1, y, BEAM) && check(x+1, y, BEAM)))
        {
            flag = false;
        }
        if (flag)
            return false;
    }
    return true;
}

---

---

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    wall = vector<vector<wall_state>>(n + 1, vector<wall_state>(n + 1, NOTHING));
    N = n + 1;
    for (auto frame : build_frame)
    {
        build(frame);
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if ((wall[i][j] & PILLAR) > 0)
            {
                answer.push_back({ i, j, 0 });
            }
            if ((wall[i][j] & BEAM) > 0)
            {
                answer.push_back({ i, j, 1 });
            }
        }
    }
    return answer;
}

결론적인 메인 솔루션 함수는 위와 같습니다.

nxn격자이기 때문에 점 단위로 생각할 때는 (n+1) x (n+1)로 다뤄야 합니다.

 

그리고 문제에서 정렬 기준에 맞게 마지막에 순회해 추가했기 때문에 별도의 정렬은 필요 없었습니다.

---

방향성은 잘 잡았었지만 부등호 실수 때문에 처음에는 몇개의 테스트를 틀렸었네요

이러한 세심함이 중요한 것 같습니다.