[BOJ][Python] 백준 1917 번: 정육면체 전개도

1일 1PS 77일차!

📚 문제

---

[골드 1] - 정육면체 전개도

💡 풀이 과정

---

• 처음에는 2차원에 정육면체의 면들이 미리 정해질 줄 알았다.

밑 오 위 왼 밑 오 
뒤 ㅡ ㅡ ㅡ ㅡ ㅡ
위 ㅡ ㅡ ㅡ ㅡ ㅡ
앞 ㅡ ㅡ ㅡ ㅡ ㅡ
밑 ㅡ ㅡ ㅡ ㅡ ㅡ
뒤 ㅡ ㅡ ㅡ ㅡ ㅡ

• 위와 같이 나열되고 6*6 입력에 맞춰 1인 부분이 6면을 나타내면 전개도라 생각했다.
• 하지만 (1, 1) 위치에 있는 면은 출발 위치에 따라 다르게 설정된다.
  • “오” 에서 내려오면 “뒤”
  • “뒤” 에서 오른쪽으로 가면 “오”

• 즉, DFS 를 통해 한칸씩 면을 결정해 나가며 출발한 면을 단서로 해당 면을 확정지어야한다.
• 각 면에서 시계방향으로 접근 가능한 면들은 다음과 같다.

밑 = [앞, 오, 뒤, 왼]
오 = [앞, 위, 뒤, 밑]
왼 = [앞, 밑, 뒤, 위]
앞 = [위, 오, 밑, 왼]
뒤 = [밑, 오, 위, 왼]
위 = [앞, 왼, 뒤 ,오]

• 각 면에서 접근할 수 있는 면의 순서는 동일하지만, 각 면에서의 offset 을 따로 구해주어야한다.
• 이를 구하기 위해서는 (이전의 면, 이전의 면을 가르키는 방향, 다음 방향) 3가지가 필요하다.
  • ㅁㅁㅁ 이렇게 가로로 이어진 전개도를 예시로 들어보자.
  • 가장 처음 ㅁ 는 “밑”으로 규정되며 다음 ㅁ 는 “오” 로 설정되어있다 가정하자.
  • 밑-오-ㅁ 여기에서 3가지는 (“밑”, “<-“ (3), “->” (1)) 이다.
  • 즉, 현재 “오” 를 기준으로 “<-“ 를 의미하는 3번 인덱스가 “밑” 에 맞게 offset 이 구해져야한다는 뜻이다.
  • 위에서 오[3] = “밑” 이므로 여기에서는 offset = 0 이다.
  • 따라서 다음 칸은 오[1 + offset] 으로 “위” 를 뜻하는 것을 알 수 있다.
• 6번의 과정을 거쳤을 때 [밑, 오, 왼, 뒤, 앞, 위] 가 중복 없이 모두 나타난다면 전개도가 생성된다는 뜻이다.

📌포인트

---

• visited
  • visited[init_x][init_y] = True 를 해줘야한다.

💻 코드

---

from collections import deque

# 위부터 시계방향 순서..
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 각 전개도 기준 시계방향에 위치한 전개도들..
cube_loc = {
    "밑": ["앞", "오", "뒤", "왼"],
    "오": ["앞", "위", "뒤", "밑"],
    "왼": ["앞", "밑", "뒤", "위"],
    "앞": ["위", "오", "밑", "왼"],
    "뒤": ["밑", "오", "위", "왼"],
    "위": ["앞", "왼", "뒤", "오"]
}

# 가장 첫 "1" 을 찾아내는 함수
def findStart():
    for i in range(6):
        for j in range(6):
            if board[i][j] == 1:
                return (i, j)


def bfs():
    # 가장 첫 "1" 의 위치를 찾아낸다.
    init_x, init_y = findStart()

    queue = deque()
    queue.clear()
    queue.append([init_x, init_y, "밑", "앞", 2])
    cube = ["밑"]

    visited = [[False for _ in range(6)] for _ in range(6)]
    visited[init_x][init_y] = True

    while queue:
        x, y, now, prev, direction = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= 6 or ny < 0 or ny >= 6 or visited[nx][ny] or board[nx][ny] == 0:
                continue

            visited[nx][ny] = True

            # cube_loc[now] 에서 (dir + 2) % 4 번쨰에 prev 가 나타나도록 변수 w 를 더해줘야한다.
            # cube_loc[now][w + (dir + 2) % 4] == prev
            a = cube_loc[now].index(prev)
            b = (direction + 2) % 4
            w = (a - b) % 4

            # 해당 위치의 블록을 구한다.
            current_block = cube_loc[now][(w + i) % 4]
            if current_block in cube:
                return "no"

            # 6면체의 전개도가 모두 구해졌으면 그대로 return 
            if len(cube) == 6:
                return "yes"
            else:
                cube.append(current_block)

            queue.append([nx, ny, current_block, now, i])

    return "yes"


for _ in range(3):
    board = [list(map(int, input().split())) for _ in range(6)]
    print(bfs())