문제: https://www.acmicpc.net/problem/12100
풀이
상하좌우 4가지로 이동할때의 함수를 만들고 dfs로 매번 상하좌우 전체의 경우를 구해본다.
그리고 5번째에 각 배열에서 최대의 값을 비교한다.
처음엔 단순무식하게 진행했다.
상하좌우 각 함수를
ex) 상(up)일 경우
- idx=1(편의상 0말고 1부터 이동)이 0일경우, 아래의 칸들을 모두 위로 1칸씩 올린다.
- idx=1이 0이 아니고 idx=2의 값과 같을경우, idx=2의 값을 0으로 바꾸고 idx=1의 값을 *2한다 그리고 idx+=1
아래의 알고리즘의 문제점은 아래의 테스트케이스에서 나타났다(14%에서 틀렸습니다. 뜸).
5
2 2 4 8 16
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 4 8 16
-> up 진행시
4 4 8 16 32
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
위의 정답결과가 아니라 아래의 결과가 나온다
2 2 4 8 16
2 2 4 8 16
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
from copy import deepcopy
N=int(input())
li=[[0]]
res=0
def up(li):
for i in range(1,N+1):
j=1
while j<N:
if j<N:
if li[j][i]==0:
ch=0
for k in range(j+1,N+1):
if li[k][i]!=0 or ch==1:
li[k-1][i],li[k][i]=li[k][i],0
ch=1
if ch==1:
j-=1
elif li[j][i]==li[j+1][i]:
li[j][i],li[j+1][i]=li[j][i]*2,0
j+=1
return li
def down(li):
for i in range(1,N+1):
j=N
while j>1:
if li[j][i]==0:
ch=0
for k in range(j-1,0,-1):
if li[k][i]!=0 or ch==1:
li[k+1][i],li[k][i]=li[k][i],0
ch=1
if ch==1:
j+=1
elif li[j][i]==li[j-1][i]:
li[j][i],li[j-1][i]=li[j][i]*2,0
j-=1
return li
def left(li):
for i in range(1,N+1):
j=1
while j<N:
if j<N:
if li[i][j]==0:
ch=0
for k in range(j+1,N+1):
if li[i][k]!=0 or ch==1:
li[i][k-1],li[i][k]=li[i][k],0
ch=1
if ch==1:
j-=1
elif li[i][j]==li[i][j+1]:
li[i][j],li[i][j+1]=li[i][j+1]*2,0
j+=1
return li
def right(li):
for i in range(1,N+1):
j=N
while j>1:
if li[i][j]==0:
ch=0
for k in range(j-1,0,-1):
if li[i][k]!=0 or ch==1:
li[i][k+1],li[i][k]=li[i][k],0
ch=1
if ch==1:
j+=1
elif li[i][j]==li[i][j-1]:
li[i][j],li[i][j-1]=li[i][j]*2,0
j-=1
return li
for i in range(N):
li.append([0]+list(map(int,input().split())))
def dfs(li,count):
global res
if count==5:
for i in range(1,N+1):
for j in range(1,N+1):
res=max(res,li[i][j])
return
dfs(up(deepcopy(li)),count+1)
dfs(down(deepcopy(li)),count+1)
dfs(left(deepcopy(li)),count+1)
dfs(right(deepcopy(li)),count+1)
dfs(li,0)
print(res)위 문제를 해결하기 위해, 머리를 굴려봤지만 코드가 너무 쓸데없이 길어져서 포인터를 이용했다.
포인터1은 첫 시작지점. 포인터2는 현재위치(for문으로 계속 옮긴다)
- 포인터1의값이 0인경우, 그자리에 포인터2(현재위치)의 값을 넣고 포인터2가 가르키는 값은 0으로 바꿔준다.
- 포인터1의값과 포인터2의 값이 같을경우, 포인터1의 값을 *2해주고 포인터1을 1칸 옮긴다.
- 그외의 경우(포인터1의값과 포인터2의 값이 다를경우), 포인터1을 증가시킨다.
from copy import deepcopy
N=int(input())
li=[[0]]
res=0
def up(li):
for i in range(1,N+1):
poi=1
for j in range(1,N+1):
if li[j][i]:
tmp,li[j][i]=li[j][i],0
if li[poi][i]==0: # 포인터위치값이 0인경우
li[poi][i]=tmp
elif li[poi][i]==tmp: #포인터위치값이 현재값과 같을경우
li[poi][i]*=2
poi+=1
else:
poi+=1
li[poi][i]=tmp
return li
def down(li):
for i in range(1,N+1):
poi=N
for j in range(N,0,-1):
if li[j][i]:
tmp,li[j][i]=li[j][i],0
if li[poi][i]==0: # 포인터위치가 0인경우
li[poi][i]=tmp
elif li[poi][i]==tmp:
li[poi][i]*=2
poi-=1
else:
poi-=1
li[poi][i]=tmp
return li
def left(li):
for i in range(1,N+1):
poi=N
for j in range(N,0,-1):
if li[i][j]:
tmp,li[i][j]=li[i][j],0
if li[i][poi]==0: # 포인터위치가 0인경우
li[i][poi]=tmp
elif li[i][poi]==tmp:
li[i][poi]*=2
poi-=1
else:
poi-=1
li[i][poi]=tmp
return li
def right(li):
for i in range(1,N+1):
poi=1
for j in range(1,N+1):
if li[i][j]:
tmp,li[i][j]=li[i][j],0
if li[i][poi]==0: # 포인터위치가 0인경우
li[i][poi]=tmp
elif li[i][poi]==tmp:
li[i][poi]*=2
poi+=1
else:
poi+=1
li[i][poi]=tmp
return li
for i in range(N):
li.append([0]+list(map(int,input().split())))
def dfs(li,count):
global res
if count==5:
for i in range(1,N+1):
for j in range(1,N+1):
res=max(res,li[i][j])
return
dfs(up(deepcopy(li)),count+1)
dfs(down(deepcopy(li)),count+1)
dfs(left(deepcopy(li)),count+1)
dfs(right(deepcopy(li)),count+1)
dfs(li,0)
print(res)
뉴비