[TIL] 24.04.16 알고리즘, 앱개발 숙련 주차 개인과제 제출

1. 알고리즘 문제 해결

 

정육면체 전개(백준 1917): 

 구현 문제였는데 말끔한 로직을 떠올리기 쉽지 않았다. 주어진 전개도에 대해 정육면체의 전개도임을 판별할 수 있는 수식이 떠오르지 않았기 때문이다. 둘레부터 시작해서, 모서리의 수, 전개도 내의 배열의 특징성 등을 떠올려봐도 정육면체의 전개도만을 판별해낼 수 있는 일반화된 식은 전혀 없었다. 그래서 시뮬레이션 방식으로 답을 찾아나가는 법 밖에는 없었다.

 일단 어느정도 복잡도를 가진 로직을 사용할 지는 몰랐지만, 아무래도 2차원 배열로 데이터가 주어지고 그 중 정사각형이 존재하는 부분만 이용하게 될 것 같았고 그렇다면 DFS/BFS와 같은 탐색류가 메인이 될 가능성이 높아보였다. 입력 데이터의 크기는 항상 6*18의 작은 크기로 주어지므로, 설령 완전탐색을 진행하더라도 큰 무리는 없어보였다.

 

 정육면체의 전개도 패턴은 제한되어 있으므로, 모든 전개도 패턴을 미리 입력해두고 모두 대조해보는 방법과 전개도 상에서 정육면체를 전개해가며 모든 면이 등장하는지 확인하는 방법 정도를 떠올릴 수 있었다. 전자보다는 후자가 조금 더 나은 방법 같아서 그 방법을 택했다.

 로직은 단순한데, 전개도 내의 정사각형이 존재하는 한 지점에서부터, 정육면체를 전개하기 시작한다. 이 때 정육면체의 각 면은 임의로 구분할 수 있어야하며, BFS를 통해서 한 면씩 전개해 나간다. 이후 모든 전개도 상에 모든 면이 등장했다면, 이는 정육면체의 전개도일 것이다.

 정육면체의 각 면은, 주사위처럼 생각하면 사고하기 편하기 때문에 이를 토대로 구현했다. 

 

 그런데 로직 자체는 금방 완성했지만, 틀렸습니다가 떠서 한동안 고생했다. 로직 상의 문제는 전혀 없어서 더 곤혹스러웠는데, 알고보니 Dice 클래스의 roll메소드들을 복사 후 수정하는 식으로 작성하다보니 인자가 제대로 안바뀐 메소드가 있어서 그랬다. 정말 이런 실수는 찾아내기 너무 힘든 것 같다..

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

class Dice{
public:
    int now, opposite, up, down, left, right;

    Dice() {
        now = 1;
        opposite = 6;
        up = 2;
        down = 5;
        left = 3;
        right = 4;
    }

    Dice(int now, int opposite, int up, int down, int left, int right) {
        this->now = now;
        this->opposite = opposite;
        this->up = up;
        this->down = down;
        this->left = left;
        this->right = right;
    }

    Dice rollUp() {
        return Dice(up, down, opposite, now, left, right);
    }

    Dice rollDown() {
        return Dice(down, up, now, opposite, left, right);
    }

    Dice rollLeft() {
        return Dice(left, right, up, down, opposite, now);
    }

    Dice rollRight() {
        return Dice(right, left, up, down, now, opposite);
    }
};

int main() {
    int map[18][6];

    pair<int, int> startPoints[3];

    for(int i=0; i<18; i++) {
        for(int j=0; j<6; j++) {
            cin >> map[i][j];
            if(map[i][j]==1) {
                startPoints[i/6] = {i, j};
            }
        }
    }

    vector<vector<bool> > isVisited(18, vector<bool>(6, false));

    for(int k=0; k<3; k++) {
        queue<pair<pair<int, int>, Dice> > q;
        q.push({startPoints[k], Dice()});
        vector<bool> isSelected(7, false);

        bool flag = true;

        while(!q.empty()) {
            Dice curDice = q.front().second;
            int curY = q.front().first.first;
            int curX = q.front().first.second;
            q.pop();

            if(isVisited[curY][curX]) continue;

            isVisited[curY][curX] = true;
            if(isSelected[curDice.now]) {
                flag = false;
                break;
            }else {
                isSelected[curDice.now] = true;

                for(int i=0; i<4; i++) {
                    int newY = curY+dy[i];
                    int newX = curX+dx[i];

                    if(newY>=0 && newY/6==k && newX>=0 && newX<6 && map[newY][newX]==1 && !isVisited[newY][newX]) {
                        Dice newDice;
                        switch (i) {
                            case 0: newDice=curDice.rollRight(); break;
                            case 1: newDice=curDice.rollDown(); break;
                            case 2: newDice=curDice.rollLeft(); break;
                            case 3: newDice=curDice.rollUp(); break;    
                        }
                        
                        q.push({{newY, newX}, newDice});
                    }
                }
            }
        }

        for(int i=1; i<=6; i++) {
            if(isSelected[i]==false) {
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "yes\n";
        }else {
            cout << "no\n";
        }
    }
}

 

2. 앱개발 숙련 주차 개인과제 마무리

 

 

 생각보다 항상 과제를 마무리해서 제출하는 시간이 길어진다. 일단 과제를 제출할 때 다양한 안드로이드 구현에 대한 질문들과 과제에 대한 회고 등을 작성해야해서, 그걸 쓰는 것부터가 좀 길어진다.

 

 

 나름 열심히 써서 내고 있는데, 아는 것을 명확하게 전달하는 과정에서 제대로 알지 못하던 부분도 많이 발견하고, 내 생각도 더 견고해지는 것 같다.

 

 그리고 아무래도 튜터님께 코드를 보여드려야 하니, gif도 넣어가며 README도 작성하고 코드 내에 부랴부랴 주석도 써넣다 보면 반나절이 금방 지나는 것 같다. 실제로 현업에서는 남과 협업 해야할 일이 잦으니, 필요한 과정일거라고 생각하고 조금 번거롭지만 계속 연습해보고 있다.

실제로 처음 README를 작성할 때보다는 많이 매끄러워 진 것 같다. 

 

 

 분명 학교 다닐 때 javaDoc이나 주석에 대한 것도 좀 배웠었는데, 이제와서 다시 써보려니 아직은 서툰 것 같다. 그래도 주석이 있으면 타인이 코드를 볼 때 훨씬 편하니까, 지금이라도 조금씩 깔끔하게 쓰는 연습을 해야겠다.

 

 오늘 원래 챌린지 반 과제도 어느정도 해두려고 했는데, 생각보다 과제 제출을 위한 준비가 길어져서 얼마나 할 수 있을지는 모르겠다. 그래도 청사진 정도는 그려둘 수 있게 해야지..