728x90
https://www.acmicpc.net/problem/9918
9918번: Cube
Folding six squares connected in some special ways can form a cube. For example, in the diagram below, the six squares on the left can be folded into a cube (with face 1 opposite face 4, face 2 opposite face 6, and face 3 opposite face 5) but the six squ
www.acmicpc.net
https://www.acmicpc.net/problem/2642
2642번: 전개도
입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나
www.acmicpc.net
22/09/25
두 문제는 완전히 동일한 문제로, 설명을 같이 할 것이다. 실제로는 전개도 문제를 먼저 풀고 Cube문제를 뒤늦게 알아 코드를 복붙 하여 문제를 해결하였다.
문제 접근 방식:
정육면체의 전개도 모양은 총 11가지 모양이 존재한다. 그 모양은 다음과 같다.
나는 이 전개도 모양 중 제일 처음 파란색 모양부터 6번째 주황색 모양까지, 180도 돌린 모양 + 뒤집은 모양 + 세로로 돌린 모양까지 모두 합쳐서 전개도가 들어있는지 들어있지 않은지 판단하는 함수인 planar_figure_form1이라는 함수를 구현했다.
이 함수는 저 6가지 전개도 중 하나가 6*6행렬에 들어가 있고, 그 순서가 1부터 6까지 잘 맞아떨어지면 1의 맞은편에 쓰여 있는 숫자를, 그렇지 않으면 0을 반환하는 함수이다.
함수의 구현은 그냥 반복문을 사용한 단순 비교+노가다이다.
마찬가지로 7번째 파란색 전개도 모양은 planar_figure_form2라는 함수로, 8번째 보라색 전개도 모양은 planar_figure_form3라는 함수로, 마지막 3개 전개도 모양은 planar_figure_form4라는 함수로 구현하였다.
결국 큐브의 전개도 모양은 이 11개 중에서 하나라도 존재하므로, 이 함수 4개를 XOR 한 값을 내보내는 cube_planar_figure이라는 함수를 만들었다.
이 함수는 1의 맞은편에 있는 숫자를 내보내는 함수이다.
나는 전개도 판단과 그래프 탐색을 동시에 진행했는데, 코드를 전개도 판단하는 코드 따로, 그래프 탐색 진행하는 코드 따로 뒀더라면 조금 짧게 구현했을 수도 있을 것 같다는 생각이 든다.
왜냐하면 1의 맞은편에 있으려면 전개도 위에서 큐브를 굴린다고 했을 때, 한 방향으로 2번 굴려야 되는 위치에 있어야 되기 때문이다.
이를 참고하여 구현하면 조금 더 짧게 구현할 수 있을 것이다.
아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.
더보기
# 2642번 전개도
# 구현, 그래프이론, 브루트포스, 그래프 탐색, DFS
'''
접근 방법:
11가지 전개도 모양을 모두 깡 구현한다.
(90도로 돌린것도 포함)
'''
num_set = set([1,2,3,4,5,6])
def planar_figure_form_1(matrix):
for row in range(1, 5):
for col in range(3):
for i in range(4):
for j in range(4):
if set([matrix[row-1][col+i], matrix[row+1][col+j], matrix[row][col],matrix[row][col+1], matrix[row][col+2], matrix[row][col+3]]) == num_set:
if matrix[row-1][col+i] == 1: return matrix[row+1][col+j]
elif matrix[row+1][col+j] == 1: return matrix[row-1][col+i]
elif matrix[row][col] == 1: return matrix[row][col+2]
elif matrix[row][col+1] == 1: return matrix[row][col+3]
elif matrix[row][col+2] == 1: return matrix[row][col]
elif matrix[row][col+3] == 1: return matrix[row][col+1]
for row in range(3):
for col in range(1, 5):
for i in range(4):
for j in range(4):
if set([matrix[row+i][col-1], matrix[row+j][col+1], matrix[row][col], matrix[row+1][col], matrix[row+2][col], matrix[row+3][col]]) == num_set:
if matrix[row+i][col-1] == 1: return matrix[row+j][col+1]
elif matrix[row+j][col+1] == 1: return matrix[row+i][col-1]
elif matrix[row][col] == 1: return matrix[row+2][col]
elif matrix[row+1][col] == 1: return matrix[row+3][col]
elif matrix[row+2][col] == 1: return matrix[row][col]
elif matrix[row+3][col] == 1: return matrix[row+1][col]
return 0
def planar_figure_form_2(matrix):
for row in range(5):
for col in range(2, 4):
if set([matrix[row+1][col-2], matrix[row+1][col-1], matrix[row+1][col], matrix[row][col], matrix[row][col+1], matrix[row][col+2]]) == num_set:
if matrix[row+1][col-2] == 1: return matrix[row+1][col]
elif matrix[row+1][col-1] == 1: return matrix[row][col+1]
elif matrix[row+1][col] == 1: return matrix[row+1][col-2]
elif matrix[row][col] == 1: return matrix[row][col+2]
elif matrix[row][col+1] == 1: return matrix[row+1][col-1]
elif matrix[row][col+2] == 1: return matrix[row][col]
elif set([matrix[row][col-2], matrix[row][col-1], matrix[row][col], matrix[row+1][col], matrix[row+1][col+1], matrix[row+1][col+2]]) == num_set:
if matrix[row][col-2] == 1: return matrix[row][col]
elif matrix[row][col-1] == 1: return matrix[row+1][col+1]
elif matrix[row][col] == 1: return matrix[row][col-2]
elif matrix[row+1][col] == 1: return matrix[row+1][col+2]
elif matrix[row+1][col+1] == 1: return matrix[row][col-1]
elif matrix[row+1][col+2] == 1: return matrix[row+1][col]
for row in range(2, 4):
for col in range(5):
if set([matrix[row-2][col+1], matrix[row-1][col+1], matrix[row][col+1], matrix[row][col], matrix[row+1][col], matrix[row+2][col]]) == num_set:
if matrix[row-2][col+1] == 1: return matrix[row][col+1]
elif matrix[row-1][col+1] == 1: return matrix[row+1][col]
elif matrix[row][col+1] == 1: return matrix[row-2][col+1]
elif matrix[row][col] == 1: return matrix[row+2][col]
elif matrix[row+1][col] == 1: return matrix[row-1][col+1]
elif matrix[row+2][col] == 1: return matrix[row][col]
elif set([matrix[row-2][col], matrix[row-1][col], matrix[row][col], matrix[row][col+1], matrix[row+1][col+1], matrix[row+2][col+1]]) == num_set:
if matrix[row-2][col] == 1: return matrix[row][col]
elif matrix[row-1][col] == 1: return matrix[row+1][col+1]
elif matrix[row][col] == 1: return matrix[row-2][col]
elif matrix[row][col+1] == 1: return matrix[row+2][col+1]
elif matrix[row+1][col+1] == 1: return matrix[row-1][col]
elif matrix[row+2][col+1] == 1: return matrix[row][col+1]
return 0
def planar_figure_form_3(matrix):
for row in range(1, 5):
for col in range(1, 4):
if set([matrix[row+1][col-1], matrix[row+1][col], matrix[row][col], matrix[row][col+1], matrix[row-1][col+1], matrix[row-1][col+2]]) == num_set:
if matrix[row+1][col-1] == 1: return matrix[row][col+1]
elif matrix[row+1][col] == 1: return matrix[row-1][col+1]
elif matrix[row][col] == 1: return matrix[row-1][col+2]
elif matrix[row][col+1] == 1: return matrix[row+1][col-1]
elif matrix[row-1][col+1] == 1: return matrix[row+1][col]
elif matrix[row-1][col+2] == 1: return matrix[row][col]
elif set([matrix[row-1][col-1], matrix[row-1][col], matrix[row][col], matrix[row][col+1], matrix[row+1][col+1], matrix[row+1][col+2]]) == num_set:
if matrix[row-1][col-1] == 1: return matrix[row][col+1]
elif matrix[row-1][col] == 1: return matrix[row+1][col+1]
elif matrix[row][col] == 1: return matrix[row+1][col+2]
elif matrix[row][col+1] == 1: return matrix[row-1][col-1]
elif matrix[row+1][col+1] == 1: return matrix[row-1][col]
elif matrix[row+1][col+2] == 1: return matrix[row][col]
for row in range(1, 4):
for col in range(1, 5):
if set([matrix[row-1][col+1], matrix[row][col+1], matrix[row][col], matrix[row+1][col], matrix[row+1][col-1], matrix[row+2][col-1]]) == num_set:
if matrix[row-1][col+1] == 1: return matrix[row+1][col]
elif matrix[row][col+1] == 1: return matrix[row+1][col-1]
elif matrix[row][col] == 1: return matrix[row+2][col-1]
elif matrix[row+1][col] == 1: return matrix[row-1][col+1]
elif matrix[row+1][col-1] == 1: return matrix[row][col+1]
elif matrix[row+2][col-1] == 1: return matrix[row][col]
elif set([matrix[row-1][col-1], matrix[row][col-1], matrix[row][col], matrix[row+1][col], matrix[row+1][col+1], matrix[row+2][col+1]]) == num_set:
if matrix[row-1][col-1] == 1: return matrix[row+1][col]
elif matrix[row][col-1] == 1: return matrix[row+1][col+1]
elif matrix[row][col] == 1: return matrix[row+2][col+1]
elif matrix[row+1][col] == 1: return matrix[row-1][col-1]
elif matrix[row+1][col+1] == 1: return matrix[row][col-1]
elif matrix[row+2][col+1] == 1: return matrix[row][col]
return 0
def planar_figure_form_4(matrix):
for row in range(1, 5):
for col in range(3):
for i in range(3):
if set([matrix[row+1][col+i], matrix[row][col], matrix[row][col+1], matrix[row][col+2], matrix[row-1][col+2], matrix[row-1][col+3]]) == num_set:
if matrix[row+1][col+i] == 1: return matrix[row-1][col+2]
elif matrix[row][col] == 1: return matrix[row][col+2]
elif matrix[row][col+1] == 1: return matrix[row-1][col+3]
elif matrix[row-1][col+2] == 1: return matrix[row+1][col+i]
elif matrix[row][col+2] == 1: return matrix[row][col]
elif matrix[row-1][col+3] == 1: return matrix[row][col+1]
for j in range(3):
if set([matrix[row-1][col+j], matrix[row][col], matrix[row][col+1], matrix[row][col+2], matrix[row+1][col+2], matrix[row+1][col+3]]) == num_set:
if matrix[row-1][col+j] == 1: return matrix[row+1][col+2]
elif matrix[row][col] == 1: return matrix[row][col+2]
elif matrix[row][col+1] == 1: return matrix[row+1][col+3]
elif matrix[row+1][col+2] == 1: return matrix[row-1][col+j]
elif matrix[row][col+2] == 1: return matrix[row][col]
elif matrix[row+1][col+3] == 1: return matrix[row][col+1]
for row in range(3):
for col in range(1, 5):
for i in range(3):
if set([matrix[row+i][col+1], matrix[row][col], matrix[row+1][col], matrix[row+2][col], matrix[row+2][col-1], matrix[row+3][col-1]]) == num_set:
if matrix[row+i][col+1] == 1: return matrix[row+2][col-1]
elif matrix[row][col] == 1: return matrix[row+2][col]
elif matrix[row+1][col] == 1: return matrix[row+3][col-1]
elif matrix[row+2][col-1] == 1: return matrix[row+i][col+1]
elif matrix[row+2][col] == 1: return matrix[row][col]
elif matrix[row+3][col-1] == 1: return matrix[row+1][col]
for j in range(3):
if set([matrix[row+j][col-1], matrix[row][col], matrix[row+1][col], matrix[row+2][col], matrix[row+2][col+1], matrix[row+3][col+1]]) == num_set:
if matrix[row+j][col-1] == 1: return matrix[row+2][col+1]
elif matrix[row][col] == 1: return matrix[row+2][col]
elif matrix[row+1][col] == 1: return matrix[row+3][col+1]
elif matrix[row+2][col+1] == 1: return matrix[row+j][col-1]
elif matrix[row+2][col] == 1: return matrix[row][col]
elif matrix[row+3][col+1] == 1: return matrix[row+1][col]
for row in range(1, 5):
for col in range(1, 4):
for i in range(3):
if set([matrix[row-1][col-1], matrix[row-1][col], matrix[row][col], matrix[row][col+1], matrix[row][col+2], matrix[row+1][col+i]]) == num_set:
if matrix[row-1][col-1] == 1: return matrix[row][col+1]
elif matrix[row-1][col] == 1: return matrix[row+1][col+i]
elif matrix[row][col] == 1: return matrix[row][col+2]
elif matrix[row][col+1] == 1: return matrix[row-1][col-1]
elif matrix[row+1][col+i] == 1: return matrix[row-1][col]
elif matrix[row][col+2] == 1: return matrix[row][col]
for j in range(3):
if set([matrix[row+1][col-1], matrix[row+1][col], matrix[row][col], matrix[row][col+1], matrix[row][col+2], matrix[row-1][col+j]]) == num_set:
if matrix[row+1][col-1] == 1: return matrix[row][col+1]
elif matrix[row+1][col] == 1: return matrix[row-1][col+j]
elif matrix[row][col] == 1: return matrix[row][col+2]
elif matrix[row][col+1] == 1: return matrix[row+1][col-1]
elif matrix[row-1][col+j] == 1: return matrix[row+1][col]
elif matrix[row][col+2] == 1: return matrix[row][col]
for row in range(1, 4):
for col in range(1, 5):
for i in range(3):
if set([matrix[row-1][col-1], matrix[row][col-1], matrix[row][col], matrix[row+1][col], matrix[row+2][col], matrix[row+i][col+1]]) == num_set:
if matrix[row-1][col-1] == 1: return matrix[row+1][col]
elif matrix[row][col-1] == 1: return matrix[row+i][col+1]
elif matrix[row][col] == 1: return matrix[row+2][col]
elif matrix[row+1][col] == 1: return matrix[row-1][col-1]
elif matrix[row+i][col+1] == 1: return matrix[row][col-1]
elif matrix[row+2][col] == 1: return matrix[row][col]
for j in range(3):
if set([matrix[row-1][col+1], matrix[row][col+1], matrix[row][col], matrix[row+1][col], matrix[row+2][col], matrix[row+j][col-1]]) == num_set:
if matrix[row-1][col+1] == 1: return matrix[row+1][col]
elif matrix[row][col+1] == 1: return matrix[row+j][col-1]
elif matrix[row][col] == 1: return matrix[row+2][col]
elif matrix[row+1][col] == 1: return matrix[row-1][col+1]
elif matrix[row+j][col-1] == 1: return matrix[row][col+1]
elif matrix[row+2][col] == 1: return matrix[row][col]
return 0
def cube_planar_figure(matrix):
return (planar_figure_form_1(matrix)^planar_figure_form_2(matrix)^
planar_figure_form_3(matrix)^planar_figure_form_4(matrix))
matrix = [list(map(int, input().split())) for _ in range(6)]
print(cube_planar_figure(matrix))'알고리즘 > 백준 문제 풀이' 카테고리의 다른 글
| [Python] 21144번 Missing Number (0) | 2022.10.21 |
|---|---|
| [Python] 21919번 소수 최소 공배수 (0) | 2022.10.21 |
| [Python] 14382번 숫자세는 양 (Large) (0) | 2022.10.21 |
| [Python] 23629번 이 얼마나 끔찍하고 무시무시한 수식이니 (0) | 2022.10.20 |
| [Python] 4349번 Blocks (0) | 2022.10.20 |