BOJ 12100. 2048 (Easy)

12100번: 2048 (Easy) (acmicpc.net)

12100번: 2048 (Easy)

 

이 문제는 예전에 유행했던 게임을 그대로 가져온 문제다.

다만 스와이프 할 때마다 랜덤한 위치에 숫자가 생성되는 기능은 구현하지 않는다.

 

5번 스와이프 했을 때 만들 수 있는 최대 수를 구하는 문제인데, 

이제 n번 했을 때의 모든 경우의 수를 따져봐야 하는 문제는 백트래킹을 이용하면 된다는 것을 이해했다.

물론 다른 방법으로 n진수를 이용하거나 할 수 있지만 백트래킹이 가장 익숙하고 또 실행시간도 빠르더라

 

처음 생각한 방식은 다음과 같다.

1. 백트래킹으로 4방향을 모두 스와이프 한다.

2. 스와이프한 결과를 다음 백트래킹으로 넘겨준다.

시간 복잡도

백트래킹 5회, 각 백트래킹당 복사 4번, 복사 소요시간 20*20, 스와이프 소요시간 20*20 을 모두 곱해주면

5*4*20*20*20*20 = 3,200,000 회가 나온다.

파이썬은 1초에 약 2천만번의 연산을 진행할 수 있으니 최악의 경우에도 약 0.2초정도가 소요될 것으로 보인다.

 

구현 중 발생한 문제

1. 백트래킹을 할 때 스와이프 이전 결과가 필요했다.

2차원 배열이므로 list.copy()보다는 copy.deepcopy()를 이용해야 한다.

또한 여기서 헷갈리는 점이 있는데 스와이프 함수에서 복사한 배열을 바꾸면 다시 배열을 반환해야하나 싶은데

DFS라서 복사한 배열을 변경하면 백트래킹에서 생성한 배열이 바뀌는 것이므로 굳이 반환할 필요가 없다.

 

구현 과정

방향에 따라 네 함수를 만들기 보다는 시작 지점을 정하는 startX, startY함수를 만들어서 사용했다.

스와이프 과정은 O(N)에 완료될 수 있게 ind가 한번 지나가면서 첫번째 숫자인지 두번째 숫자인지를 파악했고

두번째 숫자라면, 둘을 비교해 같으면 *2를 저장하고 다르면 버퍼에 존재하믄 첫번째 숫자를 두번째 숫자로 교체했다.

결과

밑의 시간 초과는, 인터넷 강의에서 설명한대로 스와이프 함수는 한 방향으로 고정하고

그 이전에 로테이트 함수를 이용해 방향을 전환시켜주는 과정을 추가해봤는데

그렇게되면 한번 돌려주는 과정이 들어가 20*20이 추가되어 시간복잡도가 1,280,000,000이 되었다.

그래서 시간 초과 발생.

아마 c++로 구현했더라면 통과하지 않았을까? 싶다. C++은 초당 1억번의 연산이 가능하니까.

 

아래는 실패한 로직