728x90
문제
카드가 추가되지 않는 NxN 크기의 2048게임을 진행한다. 최대 5번 상하좌우 네 방향으로 이동시킬 수 있을 때 보드 내의 최댓값을 구하라
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
접근
최대 다섯 번 진행될 수 있기 때문에 계속해서 방향을 바꿔서 모든 경우의 수를 탐색한다.
한 번 이동을 할 때 이미 합쳐진 수는 또다시 합쳐질 수 없다 => 표시를 해두도록 한다.
만약 연속해서 같은 숫자 3개가 있고 왼쪽으로 이동할 때 왼쪽 2개의 수가 먼저 합쳐진다. => 이동하는 방향부터 접근하여 수를 이동시킨다.
위와 같이 크게 3개의 조건을 토대로 설계를 진행하였다.
구현
- solve 함수를 통해 해를 구한다.
- 지금까지 회전의 횟수는 count가 되며 count가 다섯 번이 되었을 때 board에서 최대값을 찾아 비교한다.
- 아직 count가 다섯 번이 되지 않았을 때 상하좌우로 이동하도록 한다.
- 미리 원본 맵을 복사해두고 복사한 맵에서 이동한다.
- 복사 맵에서 이동한 결과를 다음 solve 함수를 호출한다.
def solve(board, count):
global answer
if count == 5:
for y in range(N):
for x in range(N):
answer = max(answer, board[y][x])
return
for d in range(4): # 상 하 좌 우
_board = [[0 for _ in range(N)] for _ in range(N)]
for y in range(N):
for x in range(N):
_board[y][x] = board[y][x]
move(_board, d)
solve(_board, count+1)- move함수는 보드와 이동방향을 입력받는다.
- 이동방향에 따라 탐색을 시작하는 방향이 달라지기 때문에 유의해야한다.
- 만약 0이 아닌 숫자가 나왔다면 이동하도록 한다.
- 다른 수가 나오거나 맵을 벗어난다면 이동을 종료하고
- 최종적으로 이동할 곳이 빈 칸일 때는 해당 수를 그대로 대입하고 같은 숫자일 때는 이전에 업데이트가 되었는지 여부에 따라 수를 합치거나 한 칸 전에 놓는다.
- 다른 숫자라면 한 칸 전에 있는 칸에 놓는다.
def move(board, direction):
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
updated = [[0 for _ in range(N)] for _ in range(N)]
if direction == 0:
# 위로
for x in range(N):
for y in range(N):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
elif direction == 1:
# 아래로
for x in range(N):
for y in range(N-1, -1, -1):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
elif direction == 2:
# 왼쪽으로
for y in range(N):
for x in range(N):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
else:
for y in range(N):
for x in range(N-1, -1, -1):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number전체 코드
import sys
input = sys.stdin.readline
def check_range(y, x):
return (0 <= y < N) and (0 <= x < N)
def move(board, direction):
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
updated = [[0 for _ in range(N)] for _ in range(N)]
if direction == 0:
# 위로
for x in range(N):
for y in range(N):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
elif direction == 1:
# 아래로
for x in range(N):
for y in range(N-1, -1, -1):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
elif direction == 2:
# 왼쪽으로
for y in range(N):
for x in range(N):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
else:
for y in range(N):
for x in range(N-1, -1, -1):
if board[y][x] > 0:
number = board[y][x]
board[y][x] = 0
ny = y
nx = x
while True:
if check_range(ny, nx) and board[ny][nx] == 0:
ny += dy[direction]
nx += dx[direction]
else:
if not check_range(ny, nx):
ny -= dy[direction]
nx -= dx[direction]
break
if board[ny][nx] == 0:
board[ny][nx] = number
else:
if board[ny][nx] == number and updated[ny][nx] == 0:
board[ny][nx] += number
updated[ny][nx] = 1
else:
ny -= dy[direction]
nx -= dx[direction]
board[ny][nx] = number
def solve(board, count):
global answer
if count == 5:
for y in range(N):
for x in range(N):
answer = max(answer, board[y][x])
return
for d in range(4): # 상 하 좌 우
_board = [[0 for _ in range(N)] for _ in range(N)]
for y in range(N):
for x in range(N):
_board[y][x] = board[y][x]
move(_board, d)
solve(_board, count+1)
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
answer = 0
solve(board, 0)
print(answer)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 20056] 마법사 상어와 파이어볼 (0) | 2021.07.09 |
|---|---|
| [백준 14465] 소가 길을 건너간 이유5 (0) | 2021.07.08 |
| [백준 13460] 구슬 탈출2 (0) | 2021.07.07 |
| [백준 6236] 용돈 관리 (0) | 2021.07.07 |
| [백준 2343] 기타 레슨 (0) | 2021.07.06 |