1. 문제 출처
https://www.acmicpc.net/problem/12100
2. 생각 정리
- 오른쪽, 왼쪽, 위쪽, 아래쪽 이동을 전부 다 구현하기는 너무 복잡함.
- 따라서, 행렬을 회전시켜서 하나의 이동(왼쪽)으로만 구현할 것임.
- 최대 5번 이동은 중복 순열을 사용하면 될 듯 함.
3. 조각 코드
- 행렬을 시계, 반시계 방향으로 회전하는 코드. 기억해두면 유용하게 쓰일 때가 많음
# 행렬 시계방향 90도 회전
def rotate_90():
global lst
lst = list(map(list, zip(*lst[::-1])))
# 행렬 반시계방향 90도 회전
def rotate_reverse():
global lst
lst = list(map(list, zip(*lst)))[::-1]
- 숫자들 왼쪽으로 합치는 함수
# 왼쪽으로 합치는 명령
def left():
global lst
# 0이 중간에 있는 경우 방지하기위해 0을 제일 끝으로 옮기기
for i in range(n):
if 0 in lst[i]:
cnt = 0
while 0 in lst[i]:
lst[i].remove(0)
cnt += 1
for u in range(cnt):
lst[i].append(0)
#이미 합친 부분은 또 합쳐지면 안되니까 체크하는 리스트 선언
chk = [False for _ in range(n)]
# 숫자가 같은 경우 합치고 뒤에 합쳐진 인덱스 값은 0으로 초기화.
for j in range(0,n-1):
k = j + 1
if lst[i][j] == lst[i][k] and chk[j] is False and chk[k] is False:
lst[i][j] += lst[i][k]
lst[i][k] = 0
chk[j] = True
chk[k] = True
# 다시 0이 중간에 있기때문에 0을 제일 끝으로 옮기기
if 0 in lst[i]:
cnt = 0
while 0 in lst[i]:
lst[i].remove(0)
cnt += 1
for u in range(cnt):
lst[i].append(0)
return
- 오른쪽, 위쪽, 아래쪽 명령어 함수
# 시계방향 90도를 돌려서 왼쪽으로 명령을 하면 아래쪽 명령이랑 같음.
def down():
# 90도 회전
rotate_90()
# 왼쪽 명령
left()
# 반시계 90도 회전
rotate_reverse()
return
# 시계방향 180도 돌려서 왼쪽 명령 == 오른쪽 명령
def right():
rotate_90()
rotate_90()
left()
rotate_reverse()
rotate_reverse()
return
# 시계방향 270도 돌려서 왼쪽명령 == 위쪽 명령
# 지금 생각해보니까 반대로 90도 한번 돌리는게 더 효율적일 듯 함.
def up():
rotate_90()
rotate_90()
rotate_90()
left()
rotate_reverse()
rotate_reverse()
rotate_reverse()
return
- 최대 5번 명령 경우의 수 찾기 (중복 순열 이용)
# 0,1,2,3은 각각 왼쪽, 위쪽, 아래쪽, 오른쪽 명령
cmd = [0,1,2,3]
# 0,1,2,3 중에서 중복으로 순서 상관있는 5번 뽑기
cmds = list(product(cmd,repeat=5))
# cmds = [[0,0,0,0,0], [0,0,0,0,1]...
# 리스트 깊은 복사
copys = [item[:] for item in lst]
# 순회하면서 최대값 찾기
for cmd in cmds:
lst = [item[:] for item in copys]
for a in cmd:
if a == 0:
left()
elif a == 1:
up()
elif a == 2:
down()
elif a == 3:
right()
result.append(max(map(max,lst)))
4. 전체 코드
from itertools import product
n = int(input())
lst = []
for i in range(n):
lst.append(list(map(int, input().split())))
def rotate_90():
global lst
lst = list(map(list, zip(*lst[::-1])))
def rotate_reverse():
global lst
lst = list(map(list, zip(*lst)))[::-1]
def left():
global lst
for i in range(n):
if 0 in lst[i]:
cnt = 0
while 0 in lst[i]:
lst[i].remove(0)
cnt += 1
for u in range(cnt):
lst[i].append(0)
chk = [False for _ in range(n)]
for j in range(0,n-1):
k = j + 1
if lst[i][j] == lst[i][k] and chk[j] is False and chk[k] is False:
lst[i][j] += lst[i][k]
lst[i][k] = 0
chk[j] = True
chk[k] = True
if 0 in lst[i]:
cnt = 0
while 0 in lst[i]:
lst[i].remove(0)
cnt += 1
for u in range(cnt):
lst[i].append(0)
return
def right():
rotate_90()
rotate_90()
left()
rotate_reverse()
rotate_reverse()
return
def up():
rotate_90()
rotate_90()
rotate_90()
left()
rotate_reverse()
rotate_reverse()
rotate_reverse()
return
def down():
rotate_90()
left()
rotate_reverse()
return
result = []
cmd = [0,1,2,3]
cmds = list(product(cmd,repeat=5))
copys = [item[:] for item in lst]
for cmd in cmds:
lst = [item[:] for item in copys]
for a in cmd:
if a == 0:
left()
elif a == 1:
up()
elif a == 2:
down()
elif a == 3:
right()
result.append(max(map(max,lst)))
print(max(result))
5. 마무리
- 생각보다 쉽지만은 않았던 문제.
- 이런 류의 구현 문제가 나올때 행렬 회전이 굉장히 도움 될 듯 함.(커맨드 하나로 4개 똑같은 효과)
- 최대 5번 찾을때 dfs써도 될 거 같은데, 나중에 풀땐 dfs로 풀어보려고 함.
'코딩테스트 > 백준 알고리즘 풀이' 카테고리의 다른 글
[백준 알고리즘/Python] 백준 14503번 로봇 청소기, 파이썬 설명 (0) | 2022.03.27 |
---|---|
[백준 알고리즘/Python] 백준 15686번 치킨 배달, 파이썬 설명 (0) | 2022.03.27 |
[백준 알고리즘/python] 백준 1931번 회의실배정, 파이썬 설명 (0) | 2020.09.27 |
[백준 알고리즘/python] 백준 11047번 동전 0, 파이썬 설명 (1) | 2020.09.27 |
[백준 알고리즘/python] 백준 1436번 영화감독 숌, 파이썬 설명 (0) | 2020.09.27 |
댓글