[백준/2642] 전개도 (Python)

Problem : https://www.acmicpc.net/problem/2642

2642번: 전개도

 

Difficulty : Platinum 5

 

Status : Solved

Time : 01:45:15

 

---

 

문제 설명

 

아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자. 전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.

전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다. 입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나타낸다.

 

출력

입력된 전개도를 정육면체로 접을 수 있으면, 정육면체에서 1번으로 표시된 면의 맞은 편 면의 번호를 출력하고, 정육면체로 접을 수 없으면 0을 출력한다.

 

입력 예시

0 0 0 0 0 0
0 0 0 0 0 0
0 0 5 0 0 0
0 1 2 3 4 0
0 0 6 0 0 0
0 0 0 0 0 0

 

출력 예시

3

 

 

---

 

풀이

 

주사위의 전개도 유효성 자체를 검사할 생각으로 접근했다간, 훨씬 난이도거 어려워진다. 따라서 가상의 주사위를 주어진 전개도에 따라 굴려 보며, 모든 면에 대해 검사해보면 훨씬 간단해진다. 주사위의 밑면에 지도와 마주하는 부분을 저장하고, 만약 모든 숫자를 방문할 수 없거나 혹은 이미 방문한 주사위의 밑면에 접근하게 된다면 올바르지 않은 전개도라는 이야기가 된다.

 

• dice_move : 가상의 주사위를 십자 형태로 간주하고, 상하좌우로 움직일 때마다 주사위를 회전시키는 함수이다.
• dfs : 깊이 우선 탐색을 시행하는 함수. 재귀적으로 상하좌우의 빈 칸을 탐색하여, 아직 방문하지 않은 1~6까지의 숫자가 있다면 dice_move함수로 주사위를 회전하고 탐색을 진행한다. 현재 깊이에서 이후 깊이까지 탐색하였을때 유효성 여부와 총 방문 노드 수를 반환한다.
• search : 주어진 리스트를 탐색하면서 1을 발견할 경우 dfs를 호출한다. 
• solve : 메인함수. search를 호출하여 주사위 유효성 여부를 검사하며 주사위를 완성하고, 만약 유효하다면 1의 맞은편을(1부터 탐색하였으므로 맞은편의 좌표는 무조건 고정된다), 그렇지 않다면 0을 출력한다.

 

 

 

풀이 코드

 

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
rk = [1, 0, 3, 2]

dice_map = [deque([0]*3) for _ in range(4)]
map_list = [list(map(int, input().split())) for _ in range(6)]
visited = [False]*7

def dice_move(k) :
  if k == 0 :
    dice_map[1][0], dice_map[1][1], dice_map[1][2], dice_map[3][1] = dice_map[1][1], dice_map[1][2], dice_map[3][1], dice_map[1][0]
  elif k == 1 :
    dice_map[1][0], dice_map[1][1], dice_map[1][2], dice_map[3][1] = dice_map[3][1], dice_map[1][0], dice_map[1][1], dice_map[1][2]
  elif k == 2 :
    dice_map[0][1], dice_map[1][1], dice_map[2][1], dice_map[3][1] = dice_map[1][1], dice_map[2][1], dice_map[3][1], dice_map[0][1]
  else :
    dice_map[0][1], dice_map[1][1], dice_map[2][1], dice_map[3][1] = dice_map[3][1], dice_map[0][1], dice_map[1][1], dice_map[2][1]

def dfs(x, y) :
  visited[map_list[y][x]] = True
  if dice_map[1][1] != 0 :
    return False, 0
  
  dice_map[1][1] = map_list[y][x]
  result, cnt = True, 1
  for k in range(4) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < 6 and -1 < ay < 6 and map_list[ay][ax] > 0 and not visited[map_list[ay][ax]]:
      dice_move(k)
      _result, _cnt = dfs(ax, ay)
      result &= _result
      cnt += _cnt
      dice_move(rk[k])

  return result, cnt

def search() :
  for i in range(6) :
    for j in range(6) :
      if map_list[i][j] == 1 :
        return dfs(j, i)

  return False, 0

def solve() :
  is_valid, cnt = search()
  print(0 if not is_valid or cnt != 6 else dice_map[3][1])
  return
  
solve()

풀이 완료~