문제 출처 : https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
알고리즘 분류
풀이
시뮬레이션 문제이다.
본인은 dfs+구현으로 풀었다.
우선 뎁스는 5이고 그래프의 최대 크기도 20*20이기 때문에 그래프를 상하좌우로 이동하는 로직에서 불필요한 작업만 없으면 무리 없이 통과할 것이다.
풀이는 다음과 같다.
1. dfs로 매번 상,하,좌,우로 움직이며 뎁스 5까지 탐색한다.
2. 상,하,좌,우로 이동할 때마다 원본 그래프를 깊은 복사로 복사하여 이동하고, 새로 만들어진 그래프를 다음 dfs로
넘긴다.
3. 뎁스가 5가 된다면 현재 그래프에서 최대값을 뽑아서 정답을 갱신한다.
// 블록에 적힌 수가 감소할 일은 없기 때문에 뎁스 5 상태의 그래프만 추출하면 된다.
이렇게 전체적인 풀이는 간단하나, 그래프의 이동을 구현하는 부분에서 빡! 집중을 하지 않으면 쉽게 풀 수 없다.
아래는 본인이 그래프의 이동을 구현한 방법이다.
ex) 좌로 이동할 때
합치기
합치기와 땡기기로 나누어서 구현하였다.
22202인 한 행이 있다고 하자.
이를 0부터 3까지 탐색하는데 이 인덱스를 c라고 하자.
22202 (인덱스 c의 범위)
c가 0일 때 본인을 제외한 우측 블록에서 가장 가까운 0이 아닌 블록을 찾는다.
이때 찾은 블록의 인덱스를 idx라 하자.
22202
c 블럭과 idx블럭의 숫자가 같으니 합치고 idx블럭에는 0을 넣어준다.
40202
0번째 칸은 한 번의 이동에서 더 이상 블럭이 바뀔 수 없으니 이제 c는 1을 탐색한다.
c 블럭이 0이다. 0은 빈칸이기 때문에 스킵한다.(땡기는 건 블럭을 합친 후에 하자.)
40202
c가 2일때 본인을 제외한 우측 블록에서 가장 가까운 0이 아닌 블록을 찾는다.
40202
c 블럭과 idx 블럭의 숫자가 같으니 합치고 idx블럭에는 0을 넣어준다.
40400
c블럭이 0이다. 0은 빈칸이기 때문에 스킵한다.
40400
땡기기
위의 합치는 과정에서 만들어진 행은
40400이다.
이를 이제 땡겨야 한다.
합칠 때처럼 c는 0부터 4까지 탐색한다.
40400
c가 0일 때 블럭은 4이기 때문에 땡길 수 없으니 스킵한다.
40400
c가 1일 때 블럭은 0이다. 본인을 제외한 우측 블록에서 가장 가까운 0이 아닌 블록을 찾는다.
40400
땡긴다.
44000
c가 2일 때 블럭은 0이다. 본인을 제외한 우측 블록에서 가장 가까운 0이 아닌 블록을 찾는다.
없으니 종료한다.
44000
본인은 이 문제를 통해 2048이란 게임을 알게 되었고, 지금은 장인이 됐다.
???
코드
val br = System.`in`.bufferedReader()
var answer=0
fun dfs(cnt : Int, n : Int, graph : Array<IntArray>){
if(cnt==5){
for(i in 0 until n){
answer = answer.coerceAtLeast(graph[i].maxOrNull()!!)
}
return
}
for(i in 0 until 4){
//copy
val temp = Array(n){IntArray(n)}
for(r in 0 until n){
for(c in 0 until n){
temp[r][c]=graph[r][c]
}
}
//move
when{
//상
i==0 ->{
for(c in 0 until n){
for(r in 0 until n-1){
//현재 칸에 블럭이 있는 경우 합치기
if(temp[r][c]!=0){
var idx=r+1
//아래측의 최초 블럭
while(idx<n && temp[idx][c]==0){
idx++
}
//아래측에 블럭이 없는 경우
if(idx==n) break
//숫자가 같은 경우
if(temp[r][c]==temp[idx][c]){
temp[r][c]*=2.also{temp[idx][c]=0}
}
//숫자가 다른 경우
else{
temp[r+1][c]=temp[idx][c].also{temp[idx][c]=0}
}
}
}
for(r in 0 until n-1){
//현재 칸에 블럭이 없는 경우 swap
if(temp[r][c]==0){
var idx=r+1
//아래측의 최초 블럭
while(idx<n &&temp[idx][c]==0){
idx++
}
//아래측에 블럭이 없는 경우
if(idx==n) break
//아래측에 블럭이 있는 경우 swap
temp[r][c]=temp[idx][c].also{temp[idx][c]=0}
}
}
}
}
//하
i==1 ->{
for(c in 0 until n){
for(r in n-1 downTo 1){
//현재 칸에 블럭이 있는 경우 합치기
if(temp[r][c]!=0){
var idx=r-1
//위측의 최초 블럭
while(idx>=0 && temp[idx][c]==0){
idx--
}
//위측에 블럭이 없는 경우
if(idx<0) break
//숫자가 같은 경우
if(temp[r][c]==temp[idx][c]){
temp[r][c]*=2.also{temp[idx][c]=0}
}
//숫자가 다른 경우
else{
temp[r-1][c]=temp[idx][c].also{temp[idx][c]=0}
}
}
}
for(r in n-1 downTo 1){
//현재 칸에 블럭이 없는 경우 swap
if(temp[r][c]==0){
var idx=r-1
//위측의 최초 블럭
while(idx>=0 && temp[idx][c]==0){
idx--
}
//위측에 블럭이 없는 경우
if(idx<0) break
//위측에 블럭이 있는 경우 swap
temp[r][c]=temp[idx][c].also{temp[idx][c]=0}
}
}
}
}
//좌
i==2 ->{
for(r in 0 until n){
for(c in 0 until n-1){
//현재 칸에 블럭이 있는 경우 합치기
if(temp[r][c]!=0){
var idx=c+1
//우측의 최초 블럭
while(idx<n && temp[r][idx]==0){
idx++
}
//우측에 블럭이 없는 경우
if(idx==n) break
//숫자가 같은 경우
if(temp[r][c]==temp[r][idx]){
temp[r][c]*=2.also{temp[r][idx]=0}
}
//숫자가 다른 경우
else{
temp[r][c+1]=temp[r][idx].also{temp[r][idx]=0}
}
}
}
for(c in 0 until n-1){
//현재 칸에 블럭이 없는 경우 swap
if(temp[r][c]==0){
var idx=c+1
//우측의 최초 블럭
while(idx<n && temp[r][idx]==0){
idx++
}
//우측에 블럭이 없는 경우
if(idx==n) break
//우측에 블럭이 있는 경우 swap
temp[r][c]=temp[r][idx].also{temp[r][idx]=0}
}
}
}
}
//우
i==3 ->{
for(r in 0 until n){
for(c in n-1 downTo 1){
//현재 칸에 블럭이 있는 경우 합치기
if(temp[r][c]!=0){
var idx=c-1
//좌측의 최초 블럭
while(idx>=0 && temp[r][idx]==0){
idx--
}
//좌측에 블럭이 없는 경우
if(idx<0) break
//숫자가 같은 경우
if(temp[r][c]==temp[r][idx]){
temp[r][c]*=2.also{temp[r][idx]=0}
}
//숫자가 다른 경우
else{
temp[r][c-1]=temp[r][idx].also{temp[r][idx]=0}
}
}
}
for(c in n-1 downTo 1){
//현재 칸에 블럭이 없는 경우 swap
if(temp[r][c]==0){
var idx=c-1
//좌측의 최초 블럭
while(idx>=0 && temp[r][idx]==0){
idx--
}
//좌측에 블럭이 없는 경우
if(idx<0) break
//좌측에 블럭이 있는 경우 swap
temp[r][c]=temp[r][idx].also{temp[r][idx]=0}
}
}
}
}
}//move end
dfs(cnt+1,n,temp)
}
}
fun main() =with(System.out.bufferedWriter()){
val n = br.readLine().toInt()
val graph= Array(n){br.readLine().split(' ').map{it.toInt()}.toIntArray()}
dfs(0,n,graph)
write("$answer")
close()
}'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 2239 스도쿠 Kotlin (백트래킹) (0) | 2021.12.24 |
|---|---|
| 백준 12094 2048 (Hard) Kotlin (시뮬레이션, 백트래킹) (0) | 2021.12.23 |
| 백준 11723 집합 Kotlin (구현, 비트마스킹) (0) | 2021.12.23 |
| 백준 18870 좌표 압축 Kotlin (정렬) (0) | 2021.12.23 |
| 백준 11559 Puyo Puyo Kotlin (시뮬레이션) (0) | 2021.12.22 |
댓글