백준 1930번: 정사면체 (Python/Java)

https://www.acmicpc.net/problem/1930

1930번: 정사면체

 

 

 

접근

---

두 정사면체가 같은지 확인하는 법을 구현하면 되는 문제. 간단하게 생각해보자. 정사면체는 이름 그대로 면이 네 개밖에 되지 않기 때문에 면 하나를 고정하고 그냥 순서대로 돌리면서 확인하면 된다. 예를 들어 각 면의 숫자가 1, 2, 3, 4라고 해보자. 여기서 1번 면을 바닥 면이라고 생각하면 나머지 나머지 면을 2, 3, 4라고 하든 3, 4, 2라고 하든 4, 2, 3이라고 하든 결국 똑같은 정사면체다. 이 개념을 생각한다면 그다음은 어렵지 않다.

 

우선 두 정사면체 중 같은 색상의 면이 있는지 확인한다. 같은 색상의 면이 아예 없다면 당연하게도 두 정사면체는 같은 정사면체가 아니다. 같은 색상의 면이 있다면 그 면을 바닥면으로 고정하자. 나머지 세 면을 돌려가며 상대 정사면체의 생상과 같은 순서가 나온다면 둘은 같은 정사면체다. 주의할 점은 옆면을 시계방향, 반시계 방향, 어느 방향으로 돌려도 상관없지만 순서는 반드시 지켜줘야 한다는 점이다.

 

예를 들어 기준이 되는 정사면체는 1, 2, 3, 4의 색상을, 비교할 정사면체는 3, 4, 1, 2 색상을 가지고 있다고 하자. 두 정사면체 중 같은 색상의 면을 하나 골라보자. 여기서는 3을 골라보겠다. 그렇다면 기준 정사면체는 옆면 색상이 1, 2, 4가 나온다. 이 순서는 정확하게 해줘야 한다. 똑같은 순서에서 돌리는 것은 괜찮지만 색상 순서가 바뀐다면 다른 정사면체가 되어버리기 때문이다. 이 1, 2, 4 순서는 그대로 고정해준다. 비교할 정사면체의 옆면을 돌려가며 1, 2, 4와 같은 순서가 나오는지 확인하면 된다.

 

이제 비교할 정사면체의 옆면을 구해보자. 3을 밑면으로 두면 옆면은 4, 1, 2가 된다. 이 4, 1, 2를 시계방향으로 돌리든 반시계 방향으로 돌리든 결국 같은 정사면체다. 이 경우에는 한 칸만 돌려도 1, 2, 4가 되어 기준 정사면체 배열과 같은 배열을 만들 수 있다. 이를 통해 1, 2, 3, 4 정사면체와 3, 4, 1, 2 정사면체는 같은 정사면체임을 확인할 수 있다. 이와 같은 방법을 그대로 구현하면 통과할 수 있다.

 

 

 

풀이

---

Python

firstSide = [1, 0, 0, 0]
secondSide = [2, 3, 1, 2]
thirdSide = [3, 2, 3, 1]


roundNum = int(input())

for i in range(roundNum):
    firstLine = (input()).split()
    firstBoard, secondBoard = firstLine[:4], firstLine[4:]

    result = 0
    subFirst, subSecond = [], []
    for j in range(4):
        for k in range(4):

            if firstBoard[j] == secondBoard[k]:
                subFirst = [firstBoard[firstSide[j]], firstBoard[secondSide[j]], firstBoard[thirdSide[j]]]
                subSecond = [secondBoard[firstSide[k]], secondBoard[secondSide[k]], secondBoard[thirdSide[k]]]

                for l in range(3):
                    subNum = subSecond.pop(0)
                    subSecond.append(subNum)

                    for m in range(3):
                        if subFirst[m] == subSecond[m]:
                            if m == 2:
                                result = 1
                                break
                        else:
                            break
                    
                    if result == 1:
                        break
            if result == 1:
                break
        if result == 1:
            break

    print(result)

 

Java

import java.io.IOException;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) throws IOException{
        
        Scanner scan = new Scanner(System.in);

        int[] firstSide = {1, 0, 0, 0};
        int[] secondSide = {2, 3, 1, 2};
        int[] thirdSide = {3, 2, 3, 1};

        int roundNum = Integer.parseInt(scan.nextLine());

        for(int i = 0 ; i < roundNum ; i++){
            String[] firstLine = (scan.nextLine()).split(" ");
            int[] firstBoard = new int[4], secondBoard = new int[4];
            
            for(int j = 0 ; j < 8 ; j++){
                if(j < 4){
                    firstBoard[j] = Integer.parseInt(firstLine[j]);
                }else{
                    secondBoard[j-4] = Integer.parseInt(firstLine[j]);
                }
            }

            int result = 0;
            int[] subFirst = new int[3], subSecond = new int[3];
            loop:
            for(int j = 0 ; j < 4 ; j++){
                for(int k = 0 ; k < 4 ; k++){

                    if(firstBoard[j] == secondBoard[k]){
                        subFirst = new int[] {firstBoard[firstSide[j]], firstBoard[secondSide[j]], firstBoard[thirdSide[j]]};
                        subSecond = new int[] {secondBoard[firstSide[k]], secondBoard[secondSide[k]], secondBoard[thirdSide[k]]};
                    
                        for(int l = 0 ; l < 3 ; l++){
                            int subNum = subSecond[0];
                            subSecond[0] = subSecond[1];
                            subSecond[1] = subSecond[2];
                            subSecond[2] = subNum;
                            
                            for(int m = 0 ; m < 3 ; m++){
                                if(subFirst[m] == subSecond[m]){
                                    if(m == 2){
                                        result = 1;
                                        break loop;
                                    }
                                }else{
                                    break;
                                }
                            }
    
                        }
                    }
                    
                }
            }

            System.out.println(result);

        }

    }

}

 

 

 

후기

---

우선 첫 번째로 드는 의문. 파이썬은 n 중 for문을 한 번에 빠져나갈 방법이 없는가? 연산을 줄이기 위해 for문을 break를 통해 빠져나갈 때마다 궁금증이 생겨 찾아봤는데 관련 자료를 찾지 못했다. 특히 오늘같이 3번이나 인위적으로 if와 break를 통해 for문을 빠져나가니 코드가 너무 부자연스럽게 느껴져서 '오늘만큼은 확실히 해야겠다.' 하고 구글링 해봤지만 역시 관련 자료는 찾을 수 없었다. 파이썬을 사용할 때에는 그냥 이렇게 for문을 빠져나가야 하나보다. (혹시 방법이 있다면 댓글이든 뭐든 알려주시길 부탁드립니다.)

 

두 번째로 드는 의문. 과연 이렇게 많은 for문을 중첩으로 써가며 비교하는 게 맞을 것인가? 전에도 얘기했 듯 문제를 맞히고 나면 다른 사람들의 코드 '길이'를 살펴보는 습관이 있다. 오늘은 for문을 이 정도로 중첩해서 썼을 경우에는 절대 나올 수 없는 길이의 답이 많이 제출되었다는 것을 볼 수 있었다. 내가 너무 문제 풀이를 단순하게 생각해서 코드가 이렇게 복잡하고 길어진 것인지... 반복되는 목록 비교를 어떻게 해야 보다 적은 연산을 통해 효율적으로 풀 수 있는지 확인해봐야겠다.