문제 출처 : 코드트리_2048 게임 (2048 (Easy))
티어 : 골드2
유형 : 시뮬레이션, 백트래킹
출제 : 2016년 하반기 통합 2번
주의사항 : 블럭을 합치는 순서에 주의할 것.
바로 전년도와 더불어 4방향의 중력 구현을 수행해야했던 문제입니다. 2개의 사탕을 바로 풀 수 있을 정도의 실력이시라면 크게 어렵지 않았을거라고 생각합니다. 이 기술은 앞으로도 자주 출제되므로, 잘 다룰 수 있도록 기본기를 다집시다.
생각의 흐름
격자 판이 최대 다섯 번 까지만 움직이기 때문에 백트래킹 문제라고 생각을 했습니다. 깊이가 더 깊었다면 극한의 가지치기를 요구하는 문제이거나, 혹은 백트래킹 문제가 아니었을 겁니다. 글로벌 변수로 그래프를 사용하는 방법도 있지만 재귀를 통해서 그래프를 전달하는 형식으로 백트래킹을 짜기로 마음먹고 문제를 풀었습니다.
스킬
이 문제는 중력에서 더 나아가서, 블럭을 합치는 로직을 어떻게 구현하는지가 중요합니다. 예를 들어 블럭이 아래와 같이 연달아 세 개가 있을 때,
우리는 중력을 어떻게 구현해야 할까요?
무턱대고 움직일 수 있는 왼쪽의 블럭부터 움직이게 한다면, 같은 블록을 인식할 때 합쳐지게 동작할 것이므로 그 결과는
이렇게 합쳐지게 되겠지요. 그래서 오른쪽으로 움직일 때는 오른쪽 블럭들부터, 왼쪽으로 움직일 때는 왼쪽 블럭들부터 이동시키고 합쳐야 합니다. 그러면 우리가 원하는 결과인
이런 움직임을 만들 수 있을거에요!
모든 중력의 움직임은 큐의 반복문으로 구현했습니다.
중력을 구현하였으니, 위에서 말했던 주의사항을 기억하며 풀이하겠습니다.
아, 참고로 이 문제에는 대표적으로 두 가지 풀이법이 있습니다. 하나는 이번 풀이처럼 모든 방향의 중력을 구현하는 것, 다른 하나는 한 방향만 구현한 후 그래프를 회전시켜서 네 방향 중력을 구현하는 것. 그래프 회전은 다른 문제에서 설명드릴 예정이라, 전자로 풀이했습니다.
풀이
from collections import deque
def getInput():
global N
N = int(input())
graph = []
for _ in range(N):
graph.extend(list(map(int, input().split())))
return graph
def right(temp):
# 오른쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[N*(i+1)-j-1] == 0: continue
q.append(temp[N*(i+1)-j-1])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[N*(i+1)-j-1] = ttemp[j]
return temp
def left(temp):
# 왼쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[N*i+j] == 0: continue
q.append(temp[N*i+j])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[N*i+j] = ttemp[j]
return temp
def up(temp):
# 위쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[N*j+i] == 0: continue
q.append(temp[N*j+i])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[N*j+i] = ttemp[j]
return temp
def down(temp):
# 아래쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[-N*(j+1)+i] == 0: continue
q.append(temp[-N*(j+1)+i])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[-N*(j+1)+i] = ttemp[j]
return temp
def dfs(level, temp):
# 백트래킹 함수. temp에는 그래프가 들어간다.
global maxx
if max(temp)<=maxx//(2**(5-level+1)):
return
if level == 5:
maxx = max(maxx, max(temp))
return
dfs(level+1, up(temp[:]))
dfs(level+1, down(temp[:]))
dfs(level+1, right(temp[:]))
dfs(level+1, left(temp[:]))
# ===== 실제 실행하는 부분 =====
def main():
global maxx
graph = getInput()
maxx = 0
dfs(0, graph)
print(maxx)
main()
'삼성전자 코딩테스트 기출문제 > Python' 카테고리의 다른 글
외주 수익 최대화하기 (퇴사) (2) | 2023.11.26 |
---|---|
테트리스 블럭 안의 합 최대화 하기 (테트로미노) (1) | 2023.11.25 |
정육면체 굴리기 (주사위 굴리기) (0) | 2023.11.18 |
2개의 사탕 (구슬 탈출 2) (0) | 2023.11.18 |
바이러스검사 (시험 감독) (0) | 2023.11.18 |
문제 출처 : 코드트리_2048 게임 (2048 (Easy))
티어 : 골드2
유형 : 시뮬레이션, 백트래킹
출제 : 2016년 하반기 통합 2번
주의사항 : 블럭을 합치는 순서에 주의할 것.
바로 전년도와 더불어 4방향의 중력 구현을 수행해야했던 문제입니다. 2개의 사탕을 바로 풀 수 있을 정도의 실력이시라면 크게 어렵지 않았을거라고 생각합니다. 이 기술은 앞으로도 자주 출제되므로, 잘 다룰 수 있도록 기본기를 다집시다.
생각의 흐름
격자 판이 최대 다섯 번 까지만 움직이기 때문에 백트래킹 문제라고 생각을 했습니다. 깊이가 더 깊었다면 극한의 가지치기를 요구하는 문제이거나, 혹은 백트래킹 문제가 아니었을 겁니다. 글로벌 변수로 그래프를 사용하는 방법도 있지만 재귀를 통해서 그래프를 전달하는 형식으로 백트래킹을 짜기로 마음먹고 문제를 풀었습니다.
스킬
이 문제는 중력에서 더 나아가서, 블럭을 합치는 로직을 어떻게 구현하는지가 중요합니다. 예를 들어 블럭이 아래와 같이 연달아 세 개가 있을 때,
우리는 중력을 어떻게 구현해야 할까요?
무턱대고 움직일 수 있는 왼쪽의 블럭부터 움직이게 한다면, 같은 블록을 인식할 때 합쳐지게 동작할 것이므로 그 결과는
이렇게 합쳐지게 되겠지요. 그래서 오른쪽으로 움직일 때는 오른쪽 블럭들부터, 왼쪽으로 움직일 때는 왼쪽 블럭들부터 이동시키고 합쳐야 합니다. 그러면 우리가 원하는 결과인
이런 움직임을 만들 수 있을거에요!
모든 중력의 움직임은 큐의 반복문으로 구현했습니다.
중력을 구현하였으니, 위에서 말했던 주의사항을 기억하며 풀이하겠습니다.
아, 참고로 이 문제에는 대표적으로 두 가지 풀이법이 있습니다. 하나는 이번 풀이처럼 모든 방향의 중력을 구현하는 것, 다른 하나는 한 방향만 구현한 후 그래프를 회전시켜서 네 방향 중력을 구현하는 것. 그래프 회전은 다른 문제에서 설명드릴 예정이라, 전자로 풀이했습니다.
풀이
from collections import deque
def getInput():
global N
N = int(input())
graph = []
for _ in range(N):
graph.extend(list(map(int, input().split())))
return graph
def right(temp):
# 오른쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[N*(i+1)-j-1] == 0: continue
q.append(temp[N*(i+1)-j-1])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[N*(i+1)-j-1] = ttemp[j]
return temp
def left(temp):
# 왼쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[N*i+j] == 0: continue
q.append(temp[N*i+j])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[N*i+j] = ttemp[j]
return temp
def up(temp):
# 위쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[N*j+i] == 0: continue
q.append(temp[N*j+i])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[N*j+i] = ttemp[j]
return temp
def down(temp):
# 아래쪽 중력을 구현한 함수
for i in range(N):
q = deque([])
for j in range(N):
if temp[-N*(j+1)+i] == 0: continue
q.append(temp[-N*(j+1)+i])
ttemp = deque([])
while q:
ttemp.append(q.popleft())
if q and q[0] == ttemp[-1]:
ttemp[-1] *= 2
q.popleft()
ttemp += [0]*(N-len(ttemp))
for j in range(N):
temp[-N*(j+1)+i] = ttemp[j]
return temp
def dfs(level, temp):
# 백트래킹 함수. temp에는 그래프가 들어간다.
global maxx
if max(temp)<=maxx//(2**(5-level+1)):
return
if level == 5:
maxx = max(maxx, max(temp))
return
dfs(level+1, up(temp[:]))
dfs(level+1, down(temp[:]))
dfs(level+1, right(temp[:]))
dfs(level+1, left(temp[:]))
# ===== 실제 실행하는 부분 =====
def main():
global maxx
graph = getInput()
maxx = 0
dfs(0, graph)
print(maxx)
main()
'삼성전자 코딩테스트 기출문제 > Python' 카테고리의 다른 글
외주 수익 최대화하기 (퇴사) (2) | 2023.11.26 |
---|---|
테트리스 블럭 안의 합 최대화 하기 (테트로미노) (1) | 2023.11.25 |
정육면체 굴리기 (주사위 굴리기) (0) | 2023.11.18 |
2개의 사탕 (구슬 탈출 2) (0) | 2023.11.18 |
바이러스검사 (시험 감독) (0) | 2023.11.18 |