백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12100 2048 (Easy) [ 백트래킹, DFS, 구현 ] 삼성 SW 역량 테스트 기출 문제

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 11568 민균이의 계략 [ 백트래킹, DFS, 구현 ] 삼성 SW 역량 테스트 기출 문제 

 

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

 

문제풀이 소감 🧑‍💻

 

정말 고려해야할 것들이 너무 많아서 어렵게 느껴졌다.

 

시간을 쏟을수록 쓴 시간이 아까워서 더 달려들게 되었던 문제다 ㅋㅋㅋ

 

그래도 결국 힌트없이 제 힘으로 푸는데 성공!!!! 

 

진짜 '맞았습니다!!' 떴을때 너무 기뻤다 😚😚

 

 

알고보니 삼성 SW 역량 기출문제였음..... 어쩐지 빡세더라.

 

 

 

 

 

 

 

요구사항 📋

 

* 게임 방법을 알아야하므로 문제 설명 필수 참고

 

• 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다.
• 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다.
• 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다.
• 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다.
• 블록은 적어도 하나 주어진다.
• 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

 

 

주의 ❗

 

4
0 2 0 2
2 0 0 0
0 2 2 0
2 0 2 2

 

문제 해결의 반례를 찾기 위해 만들어본 예시인데, 이 반례를 위,오른쪽,아래,왼쪽으로 각각 이동시켰을때

 

한줄이 다 4로 되어있는지를 확인하자.

 

 

위로 밀 경우

4
4 4 4 4
0 0 0 0 
0 0 0 0
0 0 0 0

 

오른쪽으로 밀 경우

4
0 0 0 4
0 0 0 4 
0 0 0 4
0 0 0 4

 

아래로 밀 경우

4
0 0 0 0
0 0 0 0 
0 0 0 0
4 4 4 4

 

왼쪽으로 밀 경우

4
4 0 0 0
4 0 0 0 
4 0 0 0
4 0 0 0

 

각각 위 경우들이 나와야한다.

 

---

 

또한,

 

4
4 2 2 4
0 0 0 0
0 0 0 0
0 0 0 0

이걸 왼쪽으로 밀었을때

 

 

4
8 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

 

이게 나오면 안된다.

 

 

4
4 4 4 0
0 0 0 0
0 0 0 0
0 0 0 0

 

이게 올바른 정답.

 

이유는 한 턴에 합쳐졌던 숫자는 다시 합치는데 쓰일 수 없다.

 

 

내가 틀렸던 부분들 정리

 

• 한 턴에 합쳐졌던 숫자는 그 턴 내에서 다시 합쳐지지 못한다.
• 합치는 것이 아닌 그냥 이동 시켜주는 경우  조건문 잘 생각 (해결 전략에서 자세히 설명)
• 숫자들 끝까지 잘 밀어주기

 

 

해결 전략 📝

 

 

1) deep copy

 

 이 문제에서 진짜 중요한 부분 중 하나가 deep copy 부분이다.

 

 

dfs 로 여러 경우를 확인해보기 때문에 원본 배열의 손상을 필수적으로 막아줘야한다. 

 

이 방법에는 deep copy가 사용된다. 얕은 복사를 해버려면 원본 배열에 손상이 생긴다.

 

 

 

자바스크립트에서 deep copy 하는 방법은 여럿 있지만, 이 방법이 가장 간편하다고 생각한다.

 

바로 copy 할 배열을 stringfy 해준다음에 parse 해주는 것이다.

 

배열이라 깊은 복사가 가능하며, 이 과정에서 객체에 대한 참조가 끊기기 때문에 이 점을 deep copy로 이용한 것이다.

 

속도가 느릴 수도 있으나 문제 풀이에 영향이 가는정도도 아니다.

 

이 과정을 거쳐줘야지 원본 값에 대한 손실이 발생하지 않으므로 특히 신경써서 구현해야하는 부분이다.

 

초기 dfs를 호출하는 부분에서만 사용하는 것이 아닌, dfs 를 재귀 호출 할때도 반드시 deep copy 해준 배열을 넣어주자.

 

 

2) 미는 방향 확인

 

 

우선 미는 방향에 따라 확인해야할 시작 인덱스들이 다르다.

 

 

0 번부터 3번까지 [ 위쪽, 오른쪽, 아래쪽, 왼쪽 ] 시계방향 순이다.

 

 

각 방향에 따른 확인해야할 인덱스는 다음과 같다.

 

---

 

 

위쪽 ⬆️

 

 

 

오른쪽 ➡️

 

 

 

 

아래쪽 ⬇️

 

 

 

 

왼쪽 ⬅️

 

 

 

향하는 방향쪽부터 시작해서 반대방향으로 진행한다고 생각하면 쉽다.

 

향하는 방향의 끝부분이 바닥이라 생각하고 차례로 하나씩 넣어준다 생각.

 

 

3) 밀어서 합치기 || 이동

 

이 문제의 구현 부분중 가장 핵심인 부분이다.

 

아마 어렵다고 느껴지거나 반례가 통과하지 못한다면 거의 이 부분의 구현에서 문제가 있을 확률이 높다.

 

 

이동 시켜줄때의 경우는 두가지다.

 

1. 같은 숫자들끼리 만나 합쳐지기

2. 빈공간으로 이동하기

 

우선 이 두가지 경우를 while 문 조건문으로 두고 돌려준다.

 

 

 

1. 같은 숫자들끼리 만나 합쳐지기 부분에서 중요한 부분은

 

한 번 합쳐진 숫자들은 그 턴 내에서 다시 합쳐질 수 없다는 것이다. 

 

이 부분을 절대 놓치지 말자.

 

이 경우를 체크해주는 방법이 바로 visited 객체를 사용해서 방문 표시를 해주는 법이다.

 

합쳐지는 경우에 그 자리에 방문 표시를 해준다.

 

이후 그 자리로 다시 숫자가 합쳐지려고 해도 방문 표시가 되어있다면 합쳐지는 행위를 막아줄 수 있다.

 

또한, 이 문제의 결국 목적은 큰 숫자를 찾는 것이므로 합쳐진 뒤의 MAX값을 저장한다.

 

 

다음은 2. 빈공간으로 이동하기 이다.

 

이 부분은 간단하다.

 

말그대로 그냥 위치만 이동시켜주면 된다. 

 

놓치지 말아야할 점은 이동 후 이동전 자리를 0으로 만들어주는 것.

 

 

 

여기서 근데 중요한 점이 있다.

 

만약 2 0 0 2 를 왼쪽으로 밀 때 어떻게 되어야 하는가?

 

당연히 4 0 0 0 이 되어야한다.

 

하지만, 2. 빈공간으로 이동하기 에는 중간 2 0 0 2 이 0 0 부분을 그냥 이동시켜준다고 판단한다.

 

그리고 다시 while 문을 돌려버리면 뜬금없이 이 0이 1. 같은 숫자들끼리 만나 합쳐지기 조건문 내로 들어가서 0 부분에 방문표시를 해버리게 될 수도 있다. (내가한 실수...)

 

쉽게 말해 0 두개가 서로 합쳐져서 그 자리에 필요없는 방문표시를 해버려 다른 숫자가 진짜 합쳐져야 할 때 합쳐지지 못하는 상황이 생겨버린다.

 

 

그러므로 이러한 상황을 막기 위해 

 

 

while 문 내의 1. 같은 숫자들끼리 만나 합쳐지기 조건 문에 nowboard[mx][my] !== 0 을 필수적으로 넣어줘야한다.

 

0 0 두개가 만난 다면 그 부분은 합치지 않겠다라고 선언하는 것이다.

 

 

 

4) 재귀 호출

 

최대 5번까지의 이동만 허락하므로 재귀가 4번 까지 추가적으로 이뤄질때까지만 dfs를 호출한다.

 

cnt<4 를 넣어주게 되면 맨 초기 호출을 제외한 4번까지만 호출을 하고 더이상 호출을 하지않게 된다.

 

또한, 이 과정에서도 원본 배열의 손상을 막기 위해 deep copy를 사용해준다.

 

 

 

 

정답 💯

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [input_N, ...input_board] = input.map((v) => v.trim().split(' ').map(Number));

function solution(N, board) {
  const direction = [0, 1, 2, 3];
  const dr_x = [-1, 0, 1, 0];
  const dr_y = [0, 1, 0, -1];

  const dfs = (nowOrder, cnt, nowBoard) => {
    let visited = {};
    if (nowOrder === 0) {
      for (let j = 0; j < N; j++) {
        for (let i = 0; i < N; i++) {
          if (check(i, j, nowOrder)) continue;
          [nowBoard, visited] = move(i, j, dr_x[nowOrder], dr_y[nowOrder], nowBoard, visited);
        }
      }
    } else if (nowOrder === 1) {
      for (let i = 0; i < N; i++) {
        for (let j = N - 1; j >= 0; j--) {
          if (check(i, j, nowOrder)) continue;
          [nowBoard, visited] = move(i, j, dr_x[nowOrder], dr_y[nowOrder], nowBoard, visited);
        }
      }
    } else if (nowOrder === 2) {
      for (let j = 0; j < N; j++) {
        for (let i = N - 1; i >= 0; i--) {
          if (check(i, j, nowOrder)) continue;
          [nowBoard, visited] = move(i, j, dr_x[nowOrder], dr_y[nowOrder], nowBoard, visited);
        }
      }
    } else if (nowOrder === 3) {
      for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
          if (check(i, j, nowOrder)) continue;
          [nowBoard, visited] = move(i, j, dr_x[nowOrder], dr_y[nowOrder], nowBoard, visited);
        }
      }
    }
    direction.forEach((dr) => {
      if (cnt < 4) {
        const copy = JSON.parse(JSON.stringify(nowBoard));
        dfs(dr, cnt + 1, copy);
      }
    });
  };

  const check = (i, j, order) => {
    return i + dr_x[order] < 0 || i + dr_x[order] >= N || j + dr_y[order] < 0 || j + dr_y[order] >= N;
  };

  const move = (x, y, drX, drY, nowboard, visited) => {
    let [mx, my] = [x, y];
    while (nowboard[mx + drX][my + drY] === 0 || nowboard[mx + drX][my + drY] === nowboard[mx][my]) {
      if (nowboard[mx + drX][my + drY] === nowboard[mx][my] && nowboard[mx][my] !== 0) {
        if (visited[`${mx + drX}${my + drY}`] === undefined) {
          nowboard[mx + drX][my + drY] *= 2;
          nowboard[mx][my] = 0;
          visited[`${mx + drX}${my + drY}`] = true;
          MAX = Math.max(MAX, nowboard[mx + drX][my + drY]);
        }
        [mx, my] = [mx + drX, my + drY];
        if (mx + drX < 0 || mx + drX >= N || my + drY < 0 || my + drY >= N) break;
        if (nowboard[mx + drX][my + drY] !== 0) break;
      } else {
        nowboard[mx + drX][my + drY] = nowboard[mx][my];
        nowboard[mx][my] = 0;
        [mx, my] = [mx + drX, my + drY];
      }
      if (mx + drX < 0 || mx + drX >= N || my + drY < 0 || my + drY >= N) break;
    }

    return [nowboard, visited];
  };

  let MAX = 0;
  board.forEach((v) => {
    MAX = Math.max(MAX, ...v);
  });
  direction.forEach((dr) => {
    const copy = JSON.parse(JSON.stringify(board));
    dfs(dr, 0, copy);
  });
  if (N === 1) return board[0][0];

  return MAX;
}

console.log(solution(input_N[0], input_board));