백준 BOJ 파이썬 1917 정육면체 전개도

14449 주사위 굴리기, 2642 전개도와 본질적으로 같은 문제다.

14449 문제는 골드4인 반면에 이 1917번 문제는 골드1이다.

이 문제는 분명 overrated되어있다고 장담한다.

왜냐하면, 인터넷에 11가지 전개도를 알아야하는 풀이법이 널리 알려져있기 때문일 것이다.

하지만, 나올지 안 나올지도 모르는 문제를 위해

11가지 전개도를 외우고 다닌다는 것은 너무 비효율적이고,

외우지 않으면 풀 수 없는 문제를 코딩테스트에 출제하지 않을 것이라 생각한다.

 

그보다 더 효율적인 풀이법은 전개도로 주사위를 굴리며 6가지의 면이

전부 바닥에 닿은 적이 있으면 전개도가 만들어지는 것이고,

1가지의 면이라도 바닥에 닿은 적이 없다면

전개도가 만들어질 수 없는 것이다.

 

 

 

일단은 기본적으로 주사위를 동,서,남,북으로 굴렸을 때 각 면이 어떻게 변하냐를 정리해야한다.

처음엔 헷갈릴 수 있다.

주사위를 굴려도 각 배열의 인덱스가 가리키는 면은 일정한데, 숫자가 다른 면으로 옮겨가는 것이다.

예를 들어 처음에 바닥면(인덱스 0)에 3이 쓰여져있었다고 해보자.

그리고, 동 쪽으로 굴리면 바닥면에 쓰여져 있던 수는 인덱스 3이 가리키는 면으로 옮겨갈 것이다.

돌아가는 구조를 이렇게 이해하면 된다.

 

주사위를 굴리는 것은 dfs로 굴리면 된다.

bfs로 굴려도 되나, 각각 큐마다 주사위 상태를 전달해줘야하고

굴렸다가 굴릴 곳이 없으면 다시 원위치로 돌아오고 다시 굴리고

이런 사고방식이 dfs를 떠올리기에 자연스러워서 dfs를 추천한다.

 

1. 1을 만나면 가장 밑면(인덱스 0)으로 간주하고 값을 1로 바꿔준다.

2. 동,서,남,북 중 하나로 굴려준다.

3.1을 만나면 가장 밑면(인덱스 0)으로 간주하고 1로 바꿔준다.

4. 계속 굴리다 4방향 탐색을 끝냈으면 전의 위치로 돌아간다.

 

여기서 주의할 점은 전의 위치로 돌아갔을 때,

주사위 위치를 또 변경해줘야한다는 점이다.

 

 

from os import kill, read, readlink, remove
import sys
from collections import deque
 
def turn(k):
    #print(s,dice)
    if k==0: ##동
        temp=dice[1]
        dice[1]=dice[2]
        dice[2]=dice[3]
        dice[3]=dice[0]
        dice[0]=temp
       # dice[0]=1
 
    elif k==1:
        temp=dice[0]
        dice[0]=dice[5]
        dice[5]=dice[2]
        dice[2]=dice[4]        
        dice[4]=temp
        
       # dice[0]=1
 
    elif k==2:
        temp=dice[1]
        dice[1]=dice[0]
        dice[0]=dice[3]
        dice[3]=dice[2]
        dice[2]=temp
        #dice[0]=1
 
    elif k==3:#북
        temp=dice[0]
        dice[0]=dice[4]
        dice[4]=dice[2]
        dice[2]=dice[5]
        dice[5]=temp
       # dice[0]=1
    dice[0]=1
 
 
def check():
    global cnt
    
    for x in dice:
        if x==0:
            print('no')
            break
    else:
        print('yes')
 
 
def dfs(x,y):
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 6*s<=nx<6*(s+1) and 0<=ny<6 and visit[nx][ny]==0 and board[nx][ny]==1:
                visit[nx][ny]=1
                turn(k)
                dfs(nx,ny)
                turn((k+2)%4)
                
 
                     
if __name__=='__main__':
    sys.stdin=open("input2.txt", "rt")
 
    board=[]
    dice=[0]*6 ##0 방문 안 함,방문 함
    ans=[0]*6
    visit=[[0]*6 for _ in range(18)]
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    cnt=0
    dQ=deque()
 
    for _ in range(18):
        board.append(list(map(int,input().split())))
 
    for s in range(3):
        for i in range(6*s,6*(s+1)):
            for j in range(6):
                if board[i][j]==1 and visit[i][j]==0:
                    visit[i][j]=1
                    dice[0]=1
                    dfs(i,j)
        check()
        dice=[0]*6 ##0 방문 안 함,방문 함