본문 바로가기
C++/백준 DFS

[c++] 2048 (Easy) (12100), 반례모음, DFS, 백트래킹, 재귀

by 스프링섬머 2023. 10. 10.
728x90
  • 열받아서 반례를 다 모아봤어요

 

반례모음
3
2 2 2
4 4 4
8 8 8 
=>16		 2
8 16
16 8
=>16		 4
8 16 0 0
0 0 16 8
0 0 0 0
0 0 0 0
=>32		 4
0 0 0 0
4 0 0 0
8 32 4 0
8 8 4 0
->64		 1
16
=> 16		 4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
=>32		 5
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 4 0 2 2
-> 32 
5
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 2 0 4 2 
-> 32 		 5
2 2 2 2 2
4 2 2 2 2
0 0 0 0 0
2 2 2 2 2
2 2 2 2 2 
-> 32 
5
4 2 2 2 2
2 2 2 2 2
0 0 0 0 0
2 2 2 2 2
2 2 2 2 2 
-> 32 
5
2 2 2 2 2
2 2 2 2 2
0 0 0 0 0
4 2 2 2 2
2 2 2 2 2
-> 32   		 4
0 4 4 32
4 0 2 64
8 8 0 0
0 16 64 4
-> 64		 3
16 2 2
2 2 2
2 2 16
-> 32		 3
2 2 2
2 2 2 
2 2 2 
=>8		 5
2 2 4 8 16
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 4 8 16
=>64		 2
16 0 
0 0
=> 16		 4
2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128
-> 128		 3
2 2 4
0 0 0
0 0 0
=> 8
10
8 8 4 16 32 0 0 8 8 8
8 8 4 0 0 8 0 0 0 0
16 0 0 16 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 16
0 0 0 0 0 0 0 0 0 2
=>128		 10
0 0 0 0 0 32 8 64 8 16
0 0 0 0 0 0 0 16 8 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
=> 128		 10
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0 
64 64 128 0 0 0 0 0 0 0
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0 
64 64 128 0 0 0 0 0 0 0
128 32 2 4 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
=> 1024		 10
16 16 8 32 32 0 0 8 8 8
16 0 0 0 0 8 0 0 0 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
->64

 

풀이
  • 구조는 쉬운데, 블록을 밀고 합하는게 너무 어려웠다.
  • 큰 틀에서 구조는 동,서,남,북 4방향으로 밀어서 합+무빙 하는데, 이를 5번 반복해서 최대 블록의 값을 얻도록 구함
  • 즉, 완전 탐색임.
  • DFS 사용해서 트리구조로 재귀 사용. 동->동->동->동->동 = 최대값 출력, 동->동->동->동->서 = 최대값 출력, ... 이렇게 반복해서 최대값 출력하면 됨
  • 여기서 중요한 것은 현재의 블록 상태를 시도(trial=최대5)마다 저장해놔야 함 -> 3차원 배열로 계속 쌓아두기
  • 여기까지는 쉽다. 5분만에 짤듯. 다음이 문제인데..
  • 블록을 무빙(밀고) 합하는 것이 매우 어려움. + 까다로운 조건까지 (한번 합한 블록은 해당 턴에 합하지 못함, 여러 개가 각각 합해질 수 있음) -> 고려해서 조건문 구성

 

 

코드

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/10.%20%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9/2048%20(Easy)%20(12100).cpp 

 

728x90

'C++ > 백준 DFS' 카테고리의 다른 글

[c++] N과 M(1~12) 유형별 정리, 백트래킹, DFS, 재귀  (1) 2023.10.09
[c++] N과 M(9) (15663), 백트래킹, 재귀, DFS  (2) 2023.10.09
[c++] 부분수열의 합(1182), 백트래킹, dfs, 재귀  (1) 2023.10.08
[C++] 백준 N-Qeen (9663), 재귀, DFS, 백트래킹  (0) 2023.10.08

관련글

티스토리툴바