[백준/1917] 정육면체 전개도 (Python)

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

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:24:29

 

---

 

문제 설명

 

 

여섯 개의 정사각형 모양의 종이가 있으면, 이를 적절히 이어 붙여서 정육면체의 전개도를 만들 수 있다. 정육면체의 전개도라는 것은, 선을 따라 종이를 적절히 접었을 때 정육면체를 완성할 수 있는 경우를 말한다.

예를 들면 아래의 모양은 정육면체의 전개도가 될 수 있다.

 

 

하지만 모든 경우에 정육면체를 만들 수 있는 것은 아니다. 예를 들어 다음과 같은 모양의 전개도는 여섯 개의 정사각형으로 이루어 있기는 하나 정육면체를 만들 수는 없다.

 

 

여섯 개의 정사각형으로 이루어진 전개도가 주어졌을 때, 이것이 정육면체의 전개도가 될 수 있는지 없는지를 가려내는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

세 개의 입력 데이터가 주어지며, 각각의 입력 데이터는 여섯 개의 줄로 이루어져 있다. 각 데이터는 여섯 개의 줄에 걸쳐 여섯 개의 숫자가 빈 칸을 사이에 두고 주어진다. 숫자는 0 또는 1로 이루어지며, 36개의 숫자 중 1은 정확히 6개가 있다. 0은 공백을 나타내며 1은 정사각형을 나타낸다. (즉 전체의 그림이 전개도를 나타낸다고 보면 된다.) 정사각형들이 서로 떨어져 있는 경우는 없다.

 

출력

 

세 개의 줄에 걸쳐, 입력된 순서대로 전개도가 정육면체의 전개도이면 yes를, 아니면 no를 출력한다.

 

입력 예시

 

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 1 1 1 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 1 1 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 1 0
0 0 1 1 0 0
0 0 0 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0

 

출력 예시

 

yes
yes
no

 

 

---

 

풀이

 

정확히 이 문제와 동일하다. 이 문제의 경우 Platinum 5 수준으로 난이도가 책정되었는데, 사실 이 문제 역시 난이도상으로는 별반 다르지 않다.

 

2023.03.09 - [알고리즘 문제/백준] - [백준/2642] 전개도 (Python)

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

 

핵심은 '가상의 주사위를 전개도를 따라 굴려보며, 주사위의 모든 면을 방문할 수 있는지' 따져보는 것이다. 위 링크에서도 비슷한 설명을 하고 있으니 관심이 있다면 한 번 읽어보도록 하자.

 

 

 

풀이 코드

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


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

def dfs(x, y) :
  cnt = 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] == 1 :
      dice_move(k)
      if not dice_visited[1][1] :
        dice_visited[1][1] = True
        cnt += dfs(ax, ay)
      dice_move(dk[k])
  return cnt

for _ in range(3) :
  map_list = [list(map(int, input().split())) for _ in range(6)]
  dice_visited = [[False]*3 for _ in range(4)]
  flg = False
  for i in range(6) :
    for j in range(6) :
      if map_list[i][j] == 1 :
        dice_visited[1][1] = True
        cnt = dfs(j, i)
        flg = True
        break
    if flg : 
      break
  print('yes' if cnt == 6 else 'no')

풀이 완료!