링크 : https://www.acmicpc.net/problem/12100
접근법 :
상하좌우로 값들을 옮겨서 합치는 게임을 모티브로 한 문제다.
규칙 1. 상하좌우 한 방향으로 모든 노드들이 움직인다.
규칙 2. 자신과 같은 값을 발견하면 더 바깥쪽에 있는 수에 안쪽에 있는 수를 더하고 안쪽의 수는 사라진다.
규칙 3. 이동하기 직전 상태를 기준으로 자신과 다른 수와는 합칠 수 없다.
접근법 1
위로 옮기는 방법을 예시로 들었을 때
1. [1,0],[1,1],[1,2],[1,3],[1,4] ... [4,3],[4,4] 순으로 진행한다.
2. 각 노드는 진행하려는 방향을 탐색한다.
3. 자신과 같은 숫자가 있으면 더하고 자신의 자리는 0으로 초기화한다. or 가장 마지막까지 아무런 수도 마주치지 못하면 마지막 자리에 노드값을 넣고 노드 자리는 초기화한다.
이런 방식은
상태 1.
결과
위와 같은 배치는 문제없지만,
상태 2.
같은 경우에는 한번 반복으로 4개 값이 모두 합쳐진
결과
이 되므로 규칙에 위배된다.
접근법 2
접근법 1에서는 [1,0]부터 시작해서 진행방향으로 노드들을 검사했지만 이번에는 진행 방향 반대로 노드를 검사한다.
시작 지점
[0,0],[0,1]...[3,3]
1. 각 노드는 진행 방향 반대로 노드들을 검사한다.
2. 자신과 같은 수가 있는지 확인하고 같은 수가 있으면 노드는 2배의 값이 되고 탐색한 노드는 0으로 초기화한다.
3. 자신의 위치를 기준으로 진행 방향쪽에 0이 있는 경우 가장 마지막 0 자리에 자신의 값을 넣고 자신은 0으로 초기화된다. 이 연산은 자신과 같은 노드를 발견하지 않았을 때도 수행한다.
진행 상태
원하는대로 움직이는 것을 알 수 있다.
※코드 진행 순서
전체 코드
https://github.com/S2econdBlue/Problem-solving/blob/main/BOJ/BOJ_12100_G2_2048_easy_answer.java
.png)
