백준 12100번 : 2048(Easy)
백준 12100번 문제 링크
백준 12100번은 한때 정말 유행했던 2048게임을 약간 변형시킨 문제다.
최초 보드에 대해 최대 5번 상,하,좌,우 방향으로 게임을 진행한 후 나올 수 있는 가장 큰 숫자를 찾는 문제이다.
1. 알고리즘 설계 :
가장 먼저 머리에 떠오른 것은 모든 경우의 수에 대해 재귀호출을 해야한다는 것이다. 물론, 한 칸에만 숫자가 존재하고 나머지는 모두 빈 칸인 경우에는 중단시켜도 되겠지만 어차피 최악의 입력에서는 발생하지지 않을 것이므로 제외시켰다.
대부분의 브루트 포스 문제와 같이 구현이 어려운 문제라서 알고리즘은 간단하다.
- 보드를 입력받는다.
- 입력된 보드를 상,하,좌,우 방향에 대해서 이동시킨다.
- 생성된 보드들에 대해서 2를 다시 진행한다.(총 5번)
- 5번 이동된 보드들의 가장 큰 숫자들을 저장해놓고 마지막에 그 중에 최대값을 출력.
+ 총 4의 5제곱 개의 정수를 저장하게 됨.
시간 복잡도 :
move(보드이동) 함수의 연산횟수 = O(n^2)
각 보드의 가장 큰 값을 구하는 반복문 = O(n^2)
두 과정이 총 1024번 반복된다.
결국, O(n^2) 이 될 것이고, 1024라는 반복횟수가 있더라도,
n의 최대값이 20이므로 1초의 실행시간을 넘길 일은 없을 것이라고 판단했다.
2. 구현과정 :
먼저 자료의 크기, 최초 보드(2차원 배열)를 입력받아야 합니다. 또, 각 보드의 최대값들을 저장할 리스트도 하나 필요합니다. 코드로는 아래와 같습니다.
N = int(input()) #보드 사이즈
BOARD = [] #입력받을 최초보드
result = [] #각 변환완료된 보드에서 가장 큰 값들을 저장할 리스트
#보드입력
for _ in range(N):
BOARD.append(list(map(int,input().split())))다음으로, 어떤 형태로 만들 것인가인데 이런 문제의 경우 재귀함수로 구현하는 것이, 대체로 가장 편한 방법입니다. 재귀함수를 구성해볼게요.
함수의 인자(parameter) 로는 무엇을 사용해야 할까
- 변경횟수가 몇 번 남은 보드인지 확인할 수 있어야 한다. -> count
- 현재보드를 2차원 리스트형태로 받아야 한다. -> tmp_board
count는 0일 때 :
더 이상 이동시키지 않아도 되는 보드이므로, 보드의 가장 큰 숫자를 찾아서 저장하고 return
count는 1이상일 때 :
4가지 방향에 대해 보드를 이동시키고, 이동시킨 보드들과
count - 1을 인자로 하여 자기 자신을 재귀호출
코드로는 아래와 같습니다.
def tzfe(tmp_board,count):
#5번 변환완료된 보드라면
if count == 0:
#보드의 최대값을 찾아서
MAX = 0
for el in tmp_board:
temp = max(el)
if temp > MAX : MAX = temp
#result에 삽입 후, 종료
result.append(MAX);return
# 4방향(상하좌우)에 대해 변환한 보드를 가지고
# count(남은 변환횟수)를 1 감소시키고
# 재귀호출
# i는 0,1,2,3(상,하,좌,우)
for i in range(4):
tzfe(move(tmp_board,i),count-1)이제 가장 까다로워보이는 이동함수 구현입니다.
먼저,이동시켜야할 보드와 이동 방향을 인자로 넘겨받아야 합니다.
보드의 사이즈는 프로그램 내에서 변하지 않으므로, 전역화해서 사용하겠습니다.
이제 깊은 복사를 사용할 것인가에 대해 생각해볼게요.
깊은 복사를 사용한다면, 인자로 넘겨받은 보드의 깊은 복사본을 만들어서 직접 수정하고 반환해도 될겁니다. 다만, 깊은 복사는 실행시간을 저해시키는 주범입니다.
따라서 인자로 들어온 board에서는 값을 참조만 하고
새로운 배열 AFTER의 이동결과를 차례차례 저장하는 것으로 계획했습니다.
문제를 살펴보면 이동을 진행할 때, 한번 합쳐진 수들은 다시 합쳐질 수 없습니다. 그래서,
마치 BFS에서 visited배열을 생성하여 이미 방문한 노드는 스킵하는 것처럼 united라는 boolean배열을 만들어서 이미 합쳐진 수들은 더 합쳐지지 않게 제어하기로 했습니다. 코드는,
def move(tmp,dir):
global N #사이즈 N을 전역변수로 사용
#변환결과를 입력할 새로운 보드
AFTER = [[0 for _ in range(N)]for _ in range(N)]
#한번 합쳐진 값들은 다시 합쳐지지 않게 하기위해, 합쳐진 적이 있는 지를 저장하는 2차원 리스트
united = [[False for _ in range(N)]for _ in range(N)]up방향으로 이동시키는 경우에 대해서만 살펴보겠습니다. 코드부터 볼까요?
#up
if dir == 0:
#i는 열, j는 행
for i in range(N):
#같은 값이 연속되어서 합쳐지거나
#연속되지 않아서 안합쳐진 채로 AFTER에 들어가야 함
#AFTER에 들어갈 때는 한쪽 벽에 쫙 붙어있어야 하므로
#place라는 변수를 벽쪽에 가까운 임계값(0 or N-1)으로 생성해서
#place자리에 넣은 후, place를 1증가시킴 => 벽쪽부터 빈자리없이 채워지게됨
place = 0
for j in range(N):
#빈칸이거나 합쳐진 적이 있는 경우 continue
if tmp[j][i] == 0 or united[j][i] : continue
#일단 넣을 자리에 현재 값 넣음
AFTER[place][i] = tmp[j][i]
#그 자리부터 벽사이에 있는 값들에 대해 탐색
for k in range(j + 1,N):
#빈칸이 아닌 것을 발견하면
if tmp[k][i] != 0:
#만약 그 값이 tmp[j][i]와 같다면
if tmp[k][i] == tmp[j][i]:
#넣었던 값을 2배(=같은 값을 합침)
AFTER[place][i] *= 2
#합친 것들은 모두 united를 True로 갱신
united[j][i] = True
united[k][i] = True
break
place += 1place는 합쳐지거나 합쳐지지 않은 수들을 각각 어떤 자리에 넣을 지 결정하는 변수입니다.
위쪽으로 이동시킬 때, ( 0, j )와 ( 1, j )가 같은 값이라면 두 수의 합을 AFTER( 0, j )에 넣어야하고
place는 0에서 1로 갱신됩니다. 그 후에 ( 1, j )는 이미 합쳐졌기 때문에 스킵하게 됩니다.
같은 방식으로 오른쪽으로 이동시키는 경우를 생각해볼까요?
place의 초기값은 무엇이 될까요? 오른쪽 벽은 인덱스상으로 board[ ][N-1]에 해당합니다.
따라서 place의 초기값은 N-1이 되고, 이후엔 N-2, N-3,...순으로 갱신됩니다.
4가지 방향 모두 진행과정은 동일하지만
반복문의 범위, 증감, place의 초기값, 조건문등이 모두 수정돼야해서 실수하기 쉽습니다.
전체코드
import sys
input = sys.stdin.readline
N = int(input()) #보드 사이즈
BOARD = [] #입력받을 최초보드
result = [] #각 변환완료된 보드에서 가장 큰 값들을 저장할 리스트
#보드입력
for _ in range(N):
BOARD.append(list(map(int,input().split())))
#상하좌우 중 한 방향으로 보드를 변환하는 함수
def move(tmp,dir):
global N #사이즈 N을 전역변수로 사용
#변환결과를 입력할 새로운 보드
AFTER = [[0 for _ in range(N)]for _ in range(N)]
#한번 합쳐진 값들은 다시 합쳐지지 않게 하기위해, 합쳐진 적이 있는 지를 저장하는 2차원 리스트
united = [[False for _ in range(N)]for _ in range(N)]
#up
if dir == 0:
#i는 열, j는 행
for i in range(N):
#같은 값이 연속되어서 합쳐지거나
#연속되지 않아서 안합쳐진 채로 AFTER에 들어가야 함
#AFTER에 들어갈 때는 한쪽 벽에 쫙 붙어있어야 하므로
#place라는 변수를 벽쪽에 가까운 임계값(0 or N-1)으로 생성해서
#place자리에 넣은 후, place를 1증가시킴 => 벽쪽부터 빈자리없이 채워지게됨
place = 0
for j in range(N):
#빈칸이거나 합쳐진 적이 있는 경우 continue
if tmp[j][i] == 0 or united[j][i] : continue
#일단 넣을 자리에 현재 값 넣음
AFTER[place][i] = tmp[j][i]
#그 자리부터 벽사이에 있는 값들에 대해 탐색
for k in range(j + 1,N):
#빈칸이 아닌 것을 발견하면
if tmp[k][i] != 0:
#만약 그 값이 tmp[j][i]와 같다면
if tmp[k][i] == tmp[j][i]:
#넣었던 값을 2배(=같은 값을 합침)
AFTER[place][i] *= 2
#합친 것들은 모두 united를 True로 갱신
united[j][i] = True
united[k][i] = True
break
place += 1
#down
elif dir == 1:
for i in range(N):
place = N-1
for j in range(N-1,-1,-1):
if tmp[j][i] == 0 or united[j][i] : continue
AFTER[place][i] = tmp[j][i]
for k in range(j-1,-1,-1):
if tmp[k][i] != 0:
if tmp[k][i] == tmp[j][i]:
AFTER[place][i] *= 2
united[j][i] = True
united[k][i] = True
break
place -= 1
#left
elif dir == 2:
for i in range(N):
place = 0
for j in range(N):
if tmp[i][j] == 0 or united[i][j] : continue
AFTER[i][place] = tmp[i][j]
for k in range(j + 1,N):
if tmp[i][k] != 0:
if tmp[i][k] == tmp[i][j]:
AFTER[i][place] *= 2
united[i][j] = True
united[i][k] = True
break
place += 1
#right
else :
for i in range(N):
place = N-1
for j in range(N-1,-1,-1):
if tmp[i][j] == 0 or united[i][j] : continue
AFTER[i][place] = tmp[i][j]
for k in range(j-1,-1,-1):
if tmp[i][k] != 0:
if tmp[i][k] == tmp[i][j]:
AFTER[i][place] *= 2
united[i][j] = True
united[i][k] = True
break
place -= 1
#변환결과(2차원배열)를 반환
return AFTER
#2048 재귀함수, 작명센스 구리네
def tzfe(tmp_board,count):
#5번 변환완료된 보드라면
if count == 0:
#보드의 최대값을 찾아서
MAX = 0
for el in tmp_board:
temp = max(el)
if temp > MAX : MAX = temp
#result에 삽입 후, 종료
result.append(MAX);return
# 4방향(상하좌우)에 대해 변환한 보드를 가지고
# count(남은 변환횟수)를 1 감소시키고
# 재귀호출
for i in range(4):
tzfe(move(tmp_board,i),count-1)
#결과
#함수실행
tzfe(BOARD,5)
#result의 최대값이 최적해
print(max(result))코드 길이가 긴건 주석이 많아서 그런 것이니 이해해주세요.
끝으로
이동함수를 구현하는 방식은 사람마다 차이가 클 것으로 생각합니다.
그래서 제가 구현한 방식이 좋은 방법인지는 잘 모르겠습니다.
다만, 인터넷 상에서 찾아본 풀이들은 모두 깊은 복사를 사용한 반면
저는 깊은 복사를 사용하지 않았기 때문에 실행시간면에서 조금 더 우수합니다.
맨 아래 제출이 제가 작성한 코드이고,
맨 위 제출이 인터넷 상에서 찾은 깊은 복사를 사용하는 코드입니다.
이제 보니 메모리도 조금 덜 썼고, 이만하면 더 좋은?거 아닐까요..? 죄송합니다.
