[BOJ] 12100 - 2048 (Easy)

사용 언어: Python3

문제

백준 12100

내 풀이

첫 번째

N = int(input())
M = [[int(x) for x in list(input().split())] for _ in range(N)]

dx,dy = [0,-1,0,1],[1,0,-1,0]
# 블록 이동
def slide(idx): # i는 dx,dy 인덱스
  if idx == 0: # 오른쪽 이동
    for i in range(N):
      tmp = [] # 0 아닌 것 담아놓음
      blankCnt = 0
      for j in range(N):
        if M[i][j] == 0:
          blankCnt += 1
        else:
          tmp.append(M[i][j])
      # 이동
      for k in range(N-len(tmp)):
        M[i][k] = 0
      for k in range(N-len(tmp),N):
        M[i][k] = tmp[k-(N-len(tmp))]
  elif idx == 1: # 위쪽 이동
    # 세로로 순회
    for j in range(N):
      tmp = [] # 0 아닌 것 담아놓음
      blankCnt = 0
      for i in range(N):
        if M[i][j] == 0:
          blankCnt += 1
        else:
          tmp.append(M[i][j])
      # 이동
      for k in range(len(tmp)):
        M[k][j] = tmp[k]
      for k in range(len(tmp),N):
        M[k][j] = 0
  elif idx == 2: # 왼쪽 이동
    for i in range(N):
      tmp = [] # 0 아닌 것 담아놓음
      blankCnt = 0
      for j in range(N):
        if M[i][j] == 0:
          blankCnt += 1
        else:
          tmp.append(M[i][j])
      # 이동
      for k in range(len(tmp)):
        M[i][k] = tmp[k]
      for k in range(len(tmp),N):
        M[i][k] = 0
  elif idx == 3: # 아래쪽 이동
    # 세로로 순회
    for j in range(N):
      tmp = [] # 0 아닌 것 담아놓음
      blankCnt = 0
      for i in range(N):
        if M[i][j] == 0:
          blankCnt += 1
        else:
          tmp.append(M[i][j])
      # 이동
      for k in range(N-len(tmp)):
        M[k][j] = 0
      for k in range(N-len(tmp), N):
        M[k][j] = tmp[k-(N-len(tmp))]
  # 각 방향 이동 후 머지      
  # merge(idx)

def merge(idx): # i는 dx,dy 인덱스
  if idx == 0: # 오른쪽 머지
    for i in range(N):
      for j in range(-1,-N+1,-1):
        if M[i][j] == M[i][j-1]:
          M[i][j] += M[i][j-1]
          M[i][j-1] = 0
  elif idx == 1: # 위로 머지
    for j in range(N):
      for i in range(N-1):
        if M[i][j] == M[i+1][j]:
          M[i][j] += M[i+1][j]
          M[i+1][j] = 0
  elif idx == 2: # 왼쪽 머지
    for i in range(N):
      for j in range(N-1):
        if M[i][j] == M[i][j+1]:
          M[i][j] += M[i][j+1]
          M[i][j+1] = 0
  elif idx == 3: # 아래로 머지
    for j in range(N):
      for i in range(-1,-N+1,-1):
        if M[i][j] == M[i-1][j]:
          M[i][j] += M[i-1][j]
          M[i-1][j] = 0
  # 각 방향 머지 후 마지막 슬라이드      
  slide(idx)


res = -1
# 5중 for문
for a in range(4):
  slide(a)
  merge(a)
  for b in range(4):
    slide(b)
    merge(b)
    for c in range(4):
      slide(c)
      merge(c)
      for d in range(4):
        slide(d)
        merge(d)
        for e in range(4):
          slide(e)
          merge(e)
          # 최대값 갱신
          for row in M:
            for val in row:
              res = max(res,val)

# 가장 큰 블록 출력
print(res)

• 예제 테스트케이스는 맞았는데 제출은 틀렸다고 나온다..
• bfs와 dfs를 사용하지 못한게 아쉬운 풀이이다

두 번째

N = int(input())
B = [list(map(int, input().split())) for _ in range(N)]

# 왼쪽으로 밀기
def slide(lst,N):
  # 0 2 2 1
  tmp = [x for x in lst if x != 0] # 0 아닌것들

  # merge
  for i in range(len(tmp)-1):
    if tmp[i] == tmp[i+1]:
      tmp[i] += tmp[i+1]
      tmp[i+1] = 0
  tmp = [x for x in tmp if x != 0]
  
  return tmp + [0] * (N-len(tmp))

# 90도 돌리기
def rotate(board, N):
  RB = [[0 for _ in range(N)] for _ in range(N)]
  for i in range(N):
    for j in range(N):
      RB[j][N-1-i] = board[i][j] # 90도 회전
  return RB

# 최대 5번 수행 후 블록 최댓값 리턴
def dfs(n,board,count):
  ret = max([max(row) for row in board])
  if count == 0:
    return ret
  for _ in range(4):
    SB = [slide(row, N) for row in board]
    if SB != board:
      ret = max(ret, dfs(N,SB,count-1))
    board = rotate(board, N) # 90도 회전
  return ret
  
# output
print(dfs(N,B,5))

다른 사람 풀이

DFS 이용

from copy import deepcopy

N = int(input())
Board = [list(map(int, input().split())) for i in range(N)] # map

# 한 방향 슬라이드만 짜고, map 자체를 돌리기
# 왼쪽 슬라이드, 90도 돌려서 왼쪽 슬라이드, 180도 돌려서 왼쪽 슬라이드, 270도 돌려서 왼쪽 슬라이드
# map을 출력하는게 아니라 최댓값을 출력하는 것이기 때문

def rotate(B, N):
  newBoard = deepcopy(B) # 기존 배열 깊은 복사
  for i in range(N):
    for j in range(N):
      newBoard[j][N-i-1] = B[i][j] # 90도 돌리는 코드 (외우면 좋음)
  return newBoard

# 슬라이드 방향 고정 (왼쪽 슬라이드시 결과)
def slide(lst, N):
  # lst = [2 2 2 2]
  tmp = [x for x in lst if x>0] # 0이 아닌 수 넣음
  for i in range(1, len(tmp)):
    if tmp[i-1] == tmp[i]:
      tmp[i-1] += tmp[i]
      tmp[i] = 0
  # lst = [4 0 4 0]
  tmp = [x for x in tmp if x>0] # 0 없애기
  # lst = [4 4]
  return tmp + [0] * (N-len(tmp)) # 나머지는 0으로 채워서 리턴
      

def dfs(N, B, count):
  ret = max([max(row) for row in B])
  if count == 0:
    return ret
  for _ in range(4):
    X = [slide(row, N) for row in B] # 슬라이드 연산
    if X != B:
      ret = max(ret, dfs(N, X, count-1))
    B = rotate(B, N) # 보드판을 90도 회전
  return ret

# output
print(dfs(N, Board, 5)) # 전역변수 최소화하기 위해 N을 파라미터로 넘김
    

• Key Point
  • 상화좌우 네 방향을 직접 짜는 것이 아니라, 방향은 한쪽으로 고정하고 map을 90도씩 돌리는 것
  • slide() 함수를 만들어서 X = [slide(row, N) for row in B]처럼 한줄로 다음 배열을 만드는 것
  • dfs에 count 제한을 걸어서 중단시키는 것

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기