BOJ_12100 2048 (Easy)
- TOC {:toc}
이 글은 백준 온라인 저지의 12100번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.
일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.
2021.08.19 (Python)
틀린 풀이입니다. 정답은 참고 답안을 참고해주세요.
| 단계 | 시작 시각 | 끝난 시각 | 걸린 시간 |
|---|---|---|---|
| 문제 이해 | 10:44:47 | 10:58:38 | |
| 풀이 생각 | 11:19:29 | 11:53:29 | |
| 코딩 | 14:52:09 | 16:59:53 | |
| 디버깅 (포기) | 21:52:38 | 22:31:23 |
from copy import deepcopy
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
res = 0
def change_index(dir, i, j):
if dir in "TD":
i, j = j, i
if dir in "RD":
j = (N - 1) - j
return i, j
def move(board, dir):
global res
changed = False
for k in range(N):
collapsed = False
new = []
now = 0
for l in range(N):
i, j = change_index(dir, k, l)
n = board[i][j]
if n:
if n == now and not collapsed:
new[-1] += n
collapsed = True
else:
new.append(n)
now = n
collapsed = False
new += [0] * (N - len(new))
for l in range(N):
tmp = new[l]
res = max(tmp, res)
i, j = change_index(dir, k, l)
if board[i][j] != tmp:
board[i][j] = tmp
changed = True
if changed:
return board
else:
return False
def dfs(board, count):
if count == 5:
return
for dir in "LTRD":
new = deepcopy(board)
new = move(new, dir)
if new:
dfs(new, count + 1)
dfs(board, 0)
print(res)
아이디어 & 풀이
상하좌우 다 돌려서 현존하는 최댓값 저장
이동했을 때 합쳐지는 함수 구현 해당 진행 방향으로 이동하면서 0이 아닌 숫자를 전부 담은 뒤 리스트 내의 연속된 숫자를 합쳐야 됨 해당 행/열 처음부터 이동하면서 현재 값이랑 리스트에서 뺴낸 값이 같고 combined가 아니면 더하고 combined 값을 True로 바꿈 그렇지 않으면 한칸 이동하고 현재 원소를 그곳에 대입 combined False 나머지는 0으로 채움
bfs나 dfs로 상하좌우로 이동시키는 경우를 탐색 더해질 요소가 있는지 체크하는 exist 관리 exist가 False이면 stack 추가하지 않고 drop 결과 리스트에 최댓값 추가하면 되겠다. 행/열을 순회하면서 exist 체크하고 업데이트 행/열도 생성하면 되겠다.
exist가 True이면 해당 배열의 결과를 현재 그리드에 반영
이동 count 세야 함 count가 5면 순회하지 않고 drop
2023.02.21 (JS)
| 단계 | 시작 시각 | 끝난 시각 | 걸린 시간 |
|---|---|---|---|
| 문제 이해 | 10:27:15 | 10:30:14 | |
| 풀이 생각 | 10:30:26 | 10:33:18 | |
| 코딩 1 | 10:33:20 | 10:53:38 | |
| 코딩 2 | 10:59:08 | 11:26:06 | |
| 코딩 3 | 11:31:27 | 11:57:44 | |
| 코딩 4 | 12:03:24 | 12:15:45 |
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
const [stringN, ...lines] = input;
const N = parseInt(stringN);
const board = lines.map((line) => line.split(" ").map((n) => parseInt(n)));
let max = 0;
function rotate(board) {
const rotated = Array.from(Array(N), () => Array(N).fill(0));
for (let i = 0; i < N; i += 1) {
for (let j = 0; j < N; j += 1) {
rotated[i][j] = board[j][N - i - 1];
}
}
return rotated;
}
// 숫자 사이의 빈 공간을 없애는 함수
function move(board) {
return board.map((row, i) => {
const newRow = row.filter((elem) => elem !== 0);
const zeros = Array(N - newRow.length).fill(0);
newRow.push(...zeros);
return newRow;
});
}
// 인접한 같은 숫자를 더하는 함수
// 해당 함수를 실행하면 빈 공간이 생기기 때문에 move를 추가로 실행해 주어야 한다
function add(board) {
for (let i = 0; i < N; i += 1) {
for (let j = 0; j < N - 1; j += 1) {
if (board[i][j] && board[i][j] === board[i][j + 1]) {
board[i][j] *= 2;
// 합쳐진 숫자는 0으로 만들어 추가로 덧셈이 일어나지 않도록 한다.
board[i][j + 1] = 0;
}
}
}
}
// 블록을 한 번 이동한 결과를 반환하는 함수
function action(board) {
let moved = board.map((nums) => [...nums]);
moved = move(moved);
add(moved);
moved = move(moved);
return moved;
}
// 두 이차원 배열이 같은지 판단하는 함수
function isEqual(arr1, arr2) {
for (let i = 0; i < N; i += 1) {
for (let j = 0; j < N; j += 1) {
if (arr1[i][j] !== arr2[i][j]) {
return false;
}
}
}
return true;
}
// 최댓값을 찾는 재귀함수
function findMax(board, count) {
max = Math.max(max, Math.max(...board.map((nums) => Math.max(...nums))));
// 최대 5번 실행하므로 count가 5가 되면 종료한다.
if (count === 5) {
return;
}
// 상하좌우 네 방향이므로 네 번 반복한다.
for (let i = 0; i < 4; i += 1) {
// 보드를 움직인 뒤
const movedBoard = action(board);
// 기존의 보드와 같지 않는 경우에만
if (!isEqual(board, movedBoard)) {
// 다음 단계로 넘어간다.
findMax(movedBoard, count + 1);
}
// 보드를 90도 회전시킨다.
board = rotate(board);
}
}
function main() {
findMax(board, 0);
return max;
}
console.log(main());
아이디어 & 풀이
우선 한 방향으로 움직였을 때 보드의 변화를 구현한다 (e.g., 왼쪽).
- 0이 아닌 숫자를 왼쪽에 모은다.
- 각 행에서 0아닌 숫자만 필터링 한 뒤
- 남은 부분은 다시 0으로 채워
- 기존의 행을 대체한다.
- 왼쪽에서부터 인접한 두 같은 수를 더한다.
- 인접한 두 수가 같으면 왼쪽의 수를 2배로 만든다.
- 오른쪽 수는 이미 합쳐진 상태이므로 우측의 블록과 연산되는 걸 막기 위해 0으로 바꾼다.
- 위의 과정을 수행하면 새로 중간에 0이 생기게 되므로 다시 0이 아닌 숫자를 왼쪽에 모은다.
위의 단위 변화를 상하좌우에 대해서 반복한다.
- 결과를 출력하는 문제가 아닌 결과값 중 최댓값을 구하는 문제이므로 움직이는 방향(함수)는 고정한 채 보드를 직접 회전시켜 결과를 구하는 것이 효율적이다.
재귀를 이용해 매 단계를 진행하면서 최댓값을 구한다.
- 최대 5번 움직인다고 했으므로
count가 5가 되면 종료한다. - 보드를 움직였을 때 변화가 없으면 (
isEqual) 더 진행하지 않는다. 즉 변화가 있는 경우에만 함수를 다시 실행한다.
디버그
max를 구하는 로직의 위치를 잘못 잡아서 모든 케이스를 커버하지 못한 것 같다.- 직접 rotate를 하지 않고
i,j좌표를 케이스 따라 반환하는 함수를 이용해 계산했는데 계속 틀린다. 아직 정확한 원인을 못 찾았다.
피드백
max값을 전역으로 관리하지 않고findMax에서 max 값을 반환하는 식으로 구현했으면 조금 더 깔끔했을 것 같다.
참고 답안 1
N = int(input())
board = [(list(map(int, input().split()))) for i in range(N)]
def rotate90(board, N):
new = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
new[j][N - i - 1] = board[i][j]
return new
def convert(lst):
new = [i for i in lst if i]
for i in range(1, len(new)):
if new[i - 1] == new[i]:
new[i - 1] *= 2
new[i] = 0
new = [i for i in new if i]
return new + [0] * (N - len(new))
def dfs(N, board, count):
ret = max(max(i) for i in board)
if count == 0:
return ret
for _ in range(4):
X = [convert(x) for x in board]
if X != board:
ret = max(ret, dfs(N, X, count - 1))
board = rotate90(board, N)
return ret
print(dfs(N, board, 5))
아이디어 & 풀이
참고 답안 2
N = int(input())
original_board = [list(map(int, input().split())) for _ in range(N)]
direction = ['l', 'u', 'r', 'd']
def max_element(matrix):
result = 0
for rows in matrix:
rows.append(result)
result = max(rows)
return result
def move_left(mat):
result = []
for rows in mat:
new_row = []
temp = 0
for num in rows:
if num == 0: continue
if temp == num:
new_row[-1] *= 2
temp = 0
else:
new_row.append(num)
temp = num
new_row += [0] * (len(rows) - len(new_row))
result.append(new_row)
return result
def move_up(mat):
result = move_left(list(map(list, zip(*mat))))
return list(map(list, zip(*result)))
def move_right(mat):
result = []
result = []
for rows in mat:
rows.reverse()
new_row = []
temp = 0
for num in rows:
if num == 0: continue
if temp == num:
new_row[-1] *= 2
temp = 0
else:
new_row.append(num)
temp = num
new_row += [0] * (len(rows) - len(new_row))
new_row.reverse()
result.append(new_row)
return result
def move_down(mat):
result = move_right(list(map(list, zip(*mat))))
return list(map(list, zip(*result)))
def dfs(board, n):
global answer
if n == 5:
answer = max(answer, max_element(board))
return
else:
dfs(move_left(board), n+1)
dfs(move_right(board), n+1)
dfs(move_up(board), n+1)
dfs(move_down(board), n+1)
answer = 0
dfs(original_board, 0)
print(answer)
아이디어 & 풀이
-
ps-python ps-js failed draft