백준 17300번 : 패턴

2yunseong·2022년 5월 16일
0

문제

출처 : https://www.acmicpc.net/problem/17300
안드로이드 OS에는 휴대폰의 잠금을 풀기 위한 방법 중 패턴을 암호로 사용하는 방법이 있다. 3×3의 9개 점에 번호를 매겨 그중 일부로 하나의 수열을 만들었을 때, 수열에서 인접한 번호의 점을 순서대로 연결해 그려지는 경로를 패턴이라 하자. 이때 패턴의 길이는 패턴을 나타내는 수열의 길이이다.

패턴에는 다음과 같은 제약이 있다.

패턴의 길이는 3 이상이다.
패턴을 나타내는 수열에는 같은 점이 두번 이상 등장하지 않는다.
수열의 인접한 점을 연결해 만든 선분 위에는 아직 등장하지 않은 점이 있을 수 없다.

예를 들어, 패턴 [1, 2, 3, 6]은 가능한 패턴이지만, [1, 3, 6]은 1-3을 연결하는 선분 위에 아직 등장하지 않은 점이 있으므로 불가능한 패턴이다. [1, 9, 6, 5]는 나중에 5가 등장하지만, 1-9를 그릴 때는 5가 등장하지 않았으므로 불가능한 패턴이며, [1, 5, 9, 6, 5]는 점이 중복해서 등장해 불가능한 패턴, [1, 5, 9, 6, 4]는 가능한 패턴이다.

패턴을 나타내는 수열이 입력되었을 때, 가능한 패턴인지 알고 싶다.

아이디어

다음과 같은 고려사항을 생각해보아야 한다.
패턴의 길이가 3인가? (길이 제약 조건이 3이상으로 주어지므로, 고려 안해도 됨)
1. 이번 방문할 점이 이미 방문 된 점인가?
2. 점과 점 사이를 이을 때, 다른 점을 지날 경우가 어떤 경우 인가?
1은 기본적인 탐색 방식에서 사용하는 방식과 같고... 2를 생각해보아야 한다.
패턴은 정사각형 모양으로 이루어져 있으므로, 꼭짓점, 변, 중앙으로 나누어서 생각해보자.
꼭짓점
꼭짓점 ~ 꼭짓점 : 두 점을 잇는 경우, 무조건 다른 점을 지난다.
꼭짓점 ~ 중앙 : 두 점이 바로 이어진다.
꼭짓점 ~ 변 : 두 점이 바로 이어진다.

변 ~ 꼭짓점 : 두 점이 바로 이어진다.
변 ~ 변 : 마주보는 두 점끼리 이으면, 무조건 중앙의 점을 경유한다. 나머지는 두 점이 바로 이어진다.
변 ~ 중앙 : 두 점이 바로 이어진다.

따라서, 꼭짓점과 꼭짓점을 이을 때, 그리고 변과 변을 이을 때를 고려해주면서 탐색해나가야 한다.

내 풀이

1. 각 점을 특징 별로 분류

    set<int> vertex ; // 꼭짓점인 점들 (정사각형에서)
    set<int> side; // 변인 점들
    int mid = 5; // 중간 점들
    
    for(int i=1; i<=9; i++){
        if(i==5) continue;
        else if(i%2 ==0){
            side.insert(i);
        } else{
            vertex.insert(i);
        }
    }

각 점을 특징별로 분류한다. 이 때, 변은 짝수, 꼭짓점은 5를 제외한 홀수인 특징에 따라 분류했다.
2. 패턴 그리기

    for(int i=0; i<patternLength; i++){
        // 방문 하지 않은 점이라면
        if(!isVisited[patterns[i]]){
            isVisited[patterns[i]] = true; // 방문했다는 표시를 남기고
            // 마지막 점이라면 종료.
            if(i == patternLength-1){
                break;
            }
 
            // 꼭지점이라면
            if(vertex.count(patterns[i]) > 0){
                // 다른 꼭짓점을 지날 때는, 경유하는 점이 이미 isVisited 가 true인지 확인해야 한다.
                if(vertex.count(patterns[i+1]) > 0){
                    if(isVertexConnect(patterns[i], patterns[i+1])){
                        continue;
                    } else {
                        isPatternRight = false;
                    }
                }   
                // 꼭짓점이 아닌 점은 바로 다음 점으로 방문 가능하다. 
                else{
                    continue;
                }
                
            }
            // 변 이라면 
            else if (side.count(patterns[i]) > 0){
                // 마주 보는 변을 지나려면 반드시 중앙점을 거쳐야 한다.
                // 따라서, isVisited[5]가 false이면, 잘못된 패턴
                if(side.count(patterns[i+1]) > 0){
                    if(isSideConnect(patterns[i], patterns[i+1])){
                        if(!isVisited[mid]){
                            isPatternRight = false; // 표시
                            break;
                        }
                    }
                }
            }
            // 중앙점이라면 무조건 방문 가능하다. 따라서 로직을 적지 않고 다음으로 지난다.
        } else { // 이미 방문 했던 점이라면 
            isPatternRight = false; // 표시
            break;
        }
    }

간단히 설명하자면 다음과 같다.
1. 지금 방문할 점이 이미 방문한 점인지 검사 (이미 방문했던 점이면 유효 패턴 X)
2. 아직 방문하지 않은 점이면, 방문했다는 점이라고 기록을 남기고 로직 수행

  • 꼭짓점 일 때
    • 꼭짓점 ~ 꼭짓점 일 때 : isVertexConnect 검사
    • 이외의 경우 : 다음 반복문 시행
  • 변 일 때
    • 서로 마주보는 변의 점 일 때 : isSideConnect 검사
    • 이외의 경우 : 다음 반복문 시행
  • 중앙 일 때
    • 다음 반복문 시행

3. isVertexConnect

bool isVertexConnect(int start, int end){
    int calc = start + end;
    bool canConnect = false;
    if(calc == 4){
        canConnect = isVisited[2];
    } else if(calc == 8){
        canConnect = isVisited[4];
    } else if(calc == 10){
        canConnect = isVisited[5];
    } else if(calc == 12){
        canConnect = isVisited[6];
    } else if(calc == 16){
        canConnect = isVisited[8];
    }
    return canConnect;
}

각 꼭짓점 끼리는 수학적인 규칙이 있다. 대표적인 건 서로 대각선 상에 위치한 꼭짓점은 서로 더하면 10이 나오므로 5를 이미 지났는지 검사해야한다. 코드를 더 줄였으면 좋으련만.. 내 생각으론 여기까지만 해도 적당하다고 생각했다.
이 전에는 모든 경우를 매핑해서 풀이했으나, if-else문이... 노가다 수준이라서 개선한 방법을 싣는다.

4. isSideConnect
마주보는 변 끼리는 이을 때 반드시 중앙점을 지난다. 그리고 마주보는 변의 점들의 두 합은 무조건 10이다. (2,8) (4,6) 따라서, 10인지만 검사해주면 되는 간단한 로직이다.

bool isSideConnect(int start, int end){
    int calc = start + end ;
    if(calc == 10){
        return true;
    }
    return false;
}

피드백

주먹구구(?) 식으로 풀다보니 if-else를 난잡하게 사용하는 것 같다. 앞으로는 노트에 정리하고 정돈된 로직을 설계해서 풀어보자.. 차근차근!
알고리즘 풀 때 메인에 로직 다 때려박는 습관 고치자... 모듈화해서 좀 풀어보자. 왜냐하면 맞았을 때는 모르겠지만 틀려서 틀린 부분을 찾을 때 시간이 좀 걸린다.. 네이밍도 신경써서 고민해보고.. 해보자
꼭짓점 - 꼭짓점에서 더 좋은 로직이 있지 않을까? 검색해서 다른 사람들의 코드를 한번 봐보자.

각 특징들을 모아놓은 집합들을 사용하긴 했지만,시간복잡도는 크게 신경쓰지 않아도 되는 문제였다. insert, count 등 기본 라이브러리 함수를 사용해도 cplusplus.com 을 참고했을 때 대충 nlogn, log 시간이라 했지만.. 사실 굳이 set을 안써도 되는 문제이고 또 최대 size라고 해보았자 4... 그래서 별 문제 없다고 생각한다. 오히려 시간복잡도보다 구현문제이니만큼 예외케이스에 대한 고려를 많이 고민해야되는 시간이였다고 생각한다.

profile
개발 발자국 남기기

0개의 댓글