https://www.acmicpc.net/problem/2549
11트만에 성공했다…
문제는 백트래킹으로 풀었습니다.
먼저, 루빅의 사각형에서 최악의 경우일때 8번을 회전하게 됩니다.
하지만 해당 문제에서는 최대로 회전하는 값이 7번으로 제한되어 있기 때문에 최악의 경우는 7번이라고 생각하면 됩니다.
다음과 같은 값이 있다고 가정해봅시다.
16 13 14 3
4 1 2 7
8 5 6 11
12 9 10 15
1행부터 4행까지 3번 회전하면 다음과 같은 값이 나옵니다.
13 14 3 16
1 2 7 4
5 6 11 8
9 10 15 12
여기서 1열과 2열, 4열을 3번 회전하면 다음과 같이 원하는 값과 일치하게 됩니다.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
문제풀이
- 변수정의
-
lubic : 입력받은 1 ~ 16으로 이루어진 타일을 저장하는 변수
-
ans : 바꾸려고 하는 형태의 타일
-
ans_cnt : 원하는 형태로 바꾸기 위한 최소 값(8인 이유는 최악의 경우의 수인 7보다 큰 수를 만들기 위함)
-
rotation : 회전한 방법을 담는 리스트 (정답)
-
tmp_rotation : 회전한 방법들을 담는 리스트 (임시)
-
diff : 정답과 다른 수의 숫자
-
change : 최상의 경우일 때 움직여서 정답에 도달할 수 있는 값 (실제 가능한 값과 다를 수는 있음)
-
prediction : 최소한으로 움직였을 때 정답에 도달할 수 있는 최소 값
-
l, line : 행, 열을 지정하는 변수
-
x, idx : 몇번째 줄인지 지정하는 변수
-
r, rotate : 몇번 회전시킬 것인지 지정하는 변수
-
Status : 회전시킬지, 회전 시킨 값을 다시 되돌릴 것인지 알려주는 변수
-
cnt : 회전시킨 횟수
- 접근방식
먼저 원하는 형태를 가진 ans라는 리스트를 만들고 입력받은 lubic과 계속해서 비교 시킵니다.
비교할 때 다른 값의 개수를 비교하고 해당 값을 diff에 담습니다.
diff가 0이라면 원하는 형태이므로 계산한 cnt와 회전한 방법을 담은 tmp_rotation 값을 rotation에 복사합니다. (tmp_rotation으로 출력을 하면 종료되지 않은 재귀때문에 원하지 않는 답을 받을 수 있습니다.)
diff가 존재한다면 diff를 4로 나눈후 1을 더한수를 change에 저장합니다.
해당 연산을 하는 이유는 최상의 경우일때 한라인의 값만 달라서 한번만 움직여도 해결 될 수 있기 때문에 4로 나눕니다. 그리고 만약 4로 나눠지지 않는 경우도 있을 수 있기 때문에 1을 더해줍니다.
그리고 현재 회전시킨 횟수와 최상의 경우일때가 현재 답보다 크다면 더이상 계산할 필요가 없기 때문에 비교하고 prediction이 더 클 경우 종료합니다.
그리고 dfs를 통해 타일을 회전시킵니다. 이때 백트래킹을 사용해서 회전한 경우를 다시 되돌려 모든 경우를 탐색할 수 있도록 해줍니다.
import sys
input = sys.stdin.readline
CONST_M = 8
lubic = [list(map(int,input().split())) for _ in range(4)]
ans = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
ans_cnt = 8
rotation = []
[rotation.append([]) for x in range(CONST_M)]
[rotation[x].append(0) for x in range(CONST_M) for y in range(3)]
tmp_rotation = []
[tmp_rotation.append([]) for x in range(CONST_M)]
[tmp_rotation[x].append(0) for x in range(CONST_M) for y in range(3)]
def lubic_check():
cnt = 0
for x in range(4):
for y in range(4):
if ans[x][y] != lubic[x][y]:
cnt += 1
return cnt
def rotate_lubic(line, idx, rotate, status):
rotate_arr = [0, 0, 0, 0]
if line == 1:
if status == False:
rotate = 4 - rotate
for i in range(4):
rotate_arr[(i + rotate) % 4] = lubic[idx][i]
for i in range(4):
lubic[idx][i] = rotate_arr[i]
else:
if status == False:
rotate = 4 - rotate
for i in range(4):
rotate_arr[(i + rotate) % 4] = lubic[i][idx]
for i in range(4):
lubic[i][idx] = rotate_arr[i]
def dfs(cnt):
global ans_cnt
diff = lubic_check()
if diff == 0 and cnt < ans_cnt:
ans_cnt = cnt
for i in range(cnt):
rotation[i][0] = tmp_rotation[i][0]
rotation[i][1] = tmp_rotation[i][1]
rotation[i][2] = tmp_rotation[i][2]
return
change = diff / 4 + 1
prediction = cnt + change
if prediction > ans_cnt:
return
for l in range(1, 3):
for x in range(4):
for r in range(1, 4):
tmp_rotation[cnt][0] = l
tmp_rotation[cnt][1] = x + 1
tmp_rotation[cnt][2] = r
rotate_lubic(l, x, r, True)
dfs(cnt + 1)
rotate_lubic(l, x, r, False)
dfs(0)
print(ans_cnt)
for i in range(ans_cnt):
print(rotation[i][0], rotation[i][1], rotation[i][2])