알고리즘 풀이 백준(BOI) 5373) 큐빙 (Python)

백준(BOI) 5373 - 큐빙

---

 

 

 

5373번: 큐빙

 

 

[ 문제풀이 ]

 

 큐빙은 큐브를 정해진 입력대로 회전시켜 윗면의 상태를 출력하는 문제로 대표적인 시뮬레이션 문제이다. 큐브 문제는 별다른 핵심적인 풀이 방법이 없는 것 같다. 그냥 주어진대로 잘 구현만 하면 된다. 그런데 그게 맘처럼 구현이 잘 안 되는 게 문제다.

 

 이 문제는 큐브를 돌리는 방법, 즉 정면을 바라보고 총 12가지 방법(U+, D+, F+, B+, R+, L+), (U-, D-, F-, B-, R-, L-)을 구현하면 된다. 한 가지 팁은 반시계 방향( - ) 은 굳이 따로 구현해줄 필요가 없다. 시계 방향으로 3번 반복해서 돌리면 반시계 방향으로 한 번 돌린 것과 결과가 같기 때문이다. 

 

 필자는 시계 방향( + ) 이 입력으로 들어올 경우 count라는 변수에 1을, 반시계 방향( - ) 이 입력으로 들어올 경우 3을 대입시켜 count 횟수만큼 move() 메소드를 돌려주었다.

 

 큐브는 3차원 배열로 구현하였다. 상단에 꼭 주석으로 큐브의 초기값을 그려보도록 하자. 참고로 이 사이트에 들어가면 큐브를 실제로 돌려보며 비교하면서 보다 편한 디버깅을 할 수 있다. 사이트에서 초기값만 문제에서 요구하는대로 바꿔주고 입력대로 돌려보면서 비교하면 된다. 

 

사이트의 모습, 필자는 큐브 모양을 구현할 모양대로 바꿔주었다.

시험장에서는 사용할 수 없으니 풀 때는 그냥 풀고 참고 목적으로만 쓰자.

 

 

 큐브 문제는 별다른 로직 없이 쌩구현이기 때문에 코드 하나하나가 치명적이다. 때문에 움직임을 구현할 때 상당한 신중함을 기울여야 한다. 배열 인덱스 하나 잘 못 입력하면 찾는데 엄청 고생한다. 때문에 이 문제는 테스트 케이스 4번까지 통과하면 웬만하면 통과하겠지만, 그렇지 않다면 디버깅을 하여 오류를 찾아내는 과정 또한 상당히 중요하다. 윗면의 출력이야 문제에서 주어지니 당연히 구현해 놨겠지만, 디버깅을 위해 큐브 전체를 출력해주는 메소드도 만들어주는 것이 좋다. 

 

 

1. 큐브를 배열에 구현한다. 문제에서 주어진 대로 초기화한다.

 

  필자는 다음과 같이 큐브를 구현하고자 하였다.

"""
               [2]
               WWW            
               WWW
               WWW
          [3]  [0]  [4]  [5]
          GGG  RRR  BBB  OOO
          GGG  RRR  BBB  OOO
          GGG  RRR  BBB  OOO
               [1]
               YYY
               YYY
               YYY  
"""

 인덱스 0은 앞면, 5는 후면, 1은 밑면, 2는 윗면, 3은 왼쪽면, 4는 오른쪽면이다.

배열을 생성해주고 초기화한다.

    cube = [[] for _ in range(6)]
    for _ in range(3):
        cube[0].append(['r','r','r']); cube[1].append(['y','y','y']); cube[2].append(['w','w','w'])
        cube[3].append(['g','g','g']); cube[4].append(['b','b','b']); cube[5].append(['o','o','o'])

 이렇게 하면 문제에서 주어진 초기 상황과 똑같아진다. 배열의 인덱스를 무엇으로 하는지에 따라 큐브의 움직임 구현을 다르게 해야 하기 때문에 생각을 잘해야 한다.

 다음은 입력을 받고 메소드에 넣어주면 된다.

...
...
	comm = list(map(str, input().split()))
...
...
	while comm: 
		go(cube,comm.pop(0))
	printResult(cube)

 입력은 큐에 받아 비워질 때까지 메소드를 돌려준다. 마지막에는 결과값(윗면)을 출력해준다.

 

 

2. 입력받은 움직임의 방향(시계방향, 반시계 방향)을 count로 치환해준다.

 

 앞서 말한 대로 반시계는 시계방향 * 3이다. 때문에 반시계 방향을 따로 구현해줄 필요가 없다. 방향을 count로 치환해주고 움직임을 구현하는 메소드로 넘긴다.

def go(cube,comm):
    direction, count = comm
    count = 1 if count == '+' else 3
    for _ in range(count): move(cube,direction)

 

 

3. 움직임을 구현해준다.

 

 문제의 가장 핵심인 시뮬레이션이다. 그냥 노가다

코드를 작성하고 잘 풀었겠지 하고 돌려보면 결과가 항상 이상하다. 99%는 인덱스의 문제였고 1%는 필자가 회전하는 면의 회전, 예를 들어 왼쪽 시계방향(L+)이라면 초록 부분을 시계방향으로 돌려주는 메소드를 실수로 3번씩 해주는 바람에 시간을 많이 낭비했다. 큐브 전체 면을 디버깅하고 나서야 알았는데, 앞서 말한 대로 이 문제는 디버깅이 매우 매우 중요하다.

 

 

 필자는 디버깅을 위해 다음과 같은 함수를 작성하고, 큐에서 명령을 빼낼 때마다 호출했다. 

    while comm: 
        go(cube,comm.pop(0))
        print("count : " , count)
        count+=1
        temp(cube)
    #printResult(cube) 주석처리
        

 

 temp()메소드가 그것이다.  다음과 같이 생겼고 다음과 같이 출력된다.

def temp(cube):
    for i in range(3):
        for j in range(3):
            print(cube[2][i][j], end="")
        print()

    for i in range(3):
        for t in range(4):
            for j in range(3):
                if t == 0:
                    print(cube[3][i][j], end="")
                elif t == 1:
                    print(cube[0][i][j], end="")
                elif t == 2:
                    print(cube[4][i][j], end="")
                elif t == 3:
                    print(cube[5][i][j], end="")
            print(" ", end=" ")
        print()
    
    for i in range(3):
        for j in range(3):
            print(cube[1][i][j], end="")
        print()
    print()

 

다음은 문제에서 주어진 테스트 케이스 중 세 번째 테스트 케이스를 넣었을 경우이다.

 

# Input >>
1
4
U- D- L+ R+

# Output >>

count :  1
www
www
www
ooo  ggg  rrr  bbb  
ggg  rrr  bbb  ooo  
ggg  rrr  bbb  ooo  
yyy
yyy
yyy

count :  2
www
www
www
ooo  ggg  rrr  bbb  
ggg  rrr  bbb  ooo  
rrr  bbb  ooo  ggg  
yyy
yyy
yyy

count :  3
gww
oww
bww
rgo  wgg  rrr  bby  
rgo  wrr  bbb  ooy  
rgo  wbb  ooo  ggy  
gyy
ryy
byy

count :  4
gwg
owr
bwb
rgo  wgy  obr  wby  
rgo  wry  obr  woy  
rgo  wby  obr  wgy  
gyg
ryo
byb

 이 문제에서 디버깅은 정말 정말 중요하다. 처음부터 통과해버리면 필요 없겠지만 정말 헤매고 헤맨다면 위에서 말한 사이트와 비교해가면서 디버깅을 해보도록 하자. 

 

 움직임은 그냥 인덱스끼리 바꿔주는 방식으로 구현하였다. 면의 움직임(L+ 일 경우 초록 면의 움직임)은 모든 면이 다 같이 쓸 수 있으므로 따로 함수로 빼서 작성하였다.

 

 이 문제는 L과 R이 구현하기 가장 어렵다. 인덱스를 거꾸로 받는 경우가 있기 때문이다. L만 보면 다음과 같고 다른 움직임도 위와 동일한 구조를 지닌다.

...
...
	elif direction == 'L': 
          temp = [cube[0][0][0], cube[0][1][0], cube[0][2][0]]
          cube[0][0][0], cube[0][1][0], cube[0][2][0] = cube[2][0][0], cube[2][1][0], cube[2][2][0]
          cube[2][0][0], cube[2][1][0], cube[2][2][0] = cube[5][2][2], cube[5][1][2], cube[5][0][2]
          cube[5][0][2], cube[5][1][2], cube[5][2][2] = cube[1][2][0], cube[1][1][0], cube[1][0][0]
          cube[1][0][0], cube[1][1][0], cube[1][2][0] = temp
          moveDimension(cube,3)
...
...

 

 해당 면의 회전은 moveDimension()에서 수행한다. 처음에 3바퀴를 회전시켰는데 생각해보니 2바퀴더라 -_-

def moveDimension(cube,index):
    for _ in range(2):
        temp = cube[index][0][0]
        cube[index][0][0] = cube[index][1][0]
        cube[index][1][0] = cube[index][2][0]
        cube[index][2][0] = cube[index][2][1]
        cube[index][2][1] = cube[index][2][2]
        cube[index][2][2] = cube[index][1][2]
        cube[index][1][2] = cube[index][0][2]
        cube[index][0][2] = cube[index][0][1]
        cube[index][0][1] = temp

 

 몇 번의 시행착오 끝에 한 번에 통과하였다. 솔직히 이 문제를 시간 안에 풀 수 있을지 의문이다. 쌩구현일 뿐더러 오류 하나하나가 치명적이기 때문이다. 디버깅을 체계적으로 잘하는 법의 필요성을 크게 느꼈던 문제였던 것 같다.

---

 

[ 전체 소스코드 ]

"""
               [2]
               WWW            
               WWW
               WWW
          [3]  [0]  [4]  [5]
          GGG  RRR  BBB  OOO
          GGG  RRR  BBB  OOO
          GGG  RRR  BBB  OOO
               [1]
               YYY
               YYY
               YYY  
"""
def printResult(cube):
    for i in range(3):
        for j in range(3):
            print(cube[2][i][j],end="")
        print()

def moveDimension(cube,index):
    for _ in range(2):
        temp = cube[index][0][0]
        cube[index][0][0] = cube[index][1][0]
        cube[index][1][0] = cube[index][2][0]
        cube[index][2][0] = cube[index][2][1]
        cube[index][2][1] = cube[index][2][2]
        cube[index][2][2] = cube[index][1][2]
        cube[index][1][2] = cube[index][0][2]
        cube[index][0][2] = cube[index][0][1]
        cube[index][0][1] = temp
    

def move(cube, direction):
    if direction == 'U':
        temp = cube[0][0]
        cube[0][0] = cube[4][0]
        cube[4][0] = cube[5][0]
        cube[5][0] = cube[3][0]
        cube[3][0] = temp
        moveDimension(cube,2)
        
    elif direction == 'D': 
        temp = cube[0][2]
        cube[0][2] = cube[3][2]
        cube[3][2] = cube[5][2]
        cube[5][2] = cube[4][2]
        cube[4][2] = temp
        moveDimension(cube,1)
        
    elif direction == 'F': 
        temp = cube[2][2]
        cube[2][2] = [cube[3][2][2], cube[3][1][2], cube[3][0][2]]
        cube[3][0][2], cube[3][1][2], cube[3][2][2] = cube[1][0]
        cube[1][0] = [cube[4][2][0], cube[4][1][0], cube[4][0][0]]
        cube[4][0][0], cube[4][1][0], cube[4][2][0] = temp
        moveDimension(cube,0)
        
    elif direction == 'B': 
        temp = cube[2][0]
        cube[2][0] = [cube[4][0][2], cube[4][1][2], cube[4][2][2]]
        cube[4][2][2], cube[4][1][2], cube[4][0][2] = cube[1][2]
        cube[1][2] = [cube[3][0][0], cube[3][1][0], cube[3][2][0]]
        cube[3][2][0], cube[3][1][0], cube[3][0][0] = temp
        moveDimension(cube,5)    
        
    elif direction == 'L': 
        temp = [cube[0][0][0], cube[0][1][0], cube[0][2][0]]
        cube[0][0][0], cube[0][1][0], cube[0][2][0] = cube[2][0][0], cube[2][1][0], cube[2][2][0]
        cube[2][0][0], cube[2][1][0], cube[2][2][0] = cube[5][2][2], cube[5][1][2], cube[5][0][2]
        cube[5][0][2], cube[5][1][2], cube[5][2][2] = cube[1][2][0], cube[1][1][0], cube[1][0][0]
        cube[1][0][0], cube[1][1][0], cube[1][2][0] = temp
        moveDimension(cube,3)
        
    elif direction == 'R': 
        temp = [cube[0][0][2], cube[0][1][2], cube[0][2][2]]
        cube[0][0][2], cube[0][1][2], cube[0][2][2] = cube[1][0][2], cube[1][1][2], cube[1][2][2]
        cube[1][0][2], cube[1][1][2], cube[1][2][2] = cube[5][2][0], cube[5][1][0], cube[5][0][0]
        cube[5][0][0], cube[5][1][0], cube[5][2][0] = cube[2][2][2], cube[2][1][2], cube[2][0][2]
        cube[2][0][2], cube[2][1][2], cube[2][2][2] = temp
        moveDimension(cube,4) 
        
def go(cube,comm):
    direction, count = comm
    count = 1 if count == '+' else 3
    for _ in range(count): move(cube,direction)


for _ in range(int(input())):
    input(); comm = list(map(str, input().split()))
    cube = [[] for _ in range(6)]
    for _ in range(3):
        cube[0].append(['r','r','r']); cube[1].append(['y','y','y']); cube[2].append(['w','w','w'])
        cube[3].append(['g','g','g']); cube[4].append(['b','b','b']); cube[5].append(['o','o','o'])
    while comm: 
        go(cube,comm.pop(0))
    printResult(cube)