[코딩테스트]백준 - 숫자판 점프

숫자판 점프

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

예제 입력 1

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

예제 출력 1

15

힌트

111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

알고리즘 분류

• 백트래킹

해결한 코드

function b2210() {
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
  
    var link = []
    for (var k = 0; k < input.length; k++) {
        link.push(input[k].split(' ').map(e => e / 1))
    }
  
    var ans = []
    for(var i=0; i<5; i++){
    	for(var j=0; j<5; j++){
          backTrack(link, ans, link[i][j].toString(), i, j)
        }
    }
  console.log(ans.length)
}
 
function backTrack(link, ans, str, x, y){
  var dx = [1, -1, 0, 0]
  var dy = [0, 0, 1, -1]
    
  if(str.length === 6){
    if(ans.every(e=> e !== str)){
      ans.push(str)
    }
   return ans;
  }
  
  for(var i=0; i<4; i++){
    if(x+dx[i] >= 0 && x+dx[i] < 5 && y+dy[i] >= 0 && y+dy[i] < 5){
    	backTrack(link, ans, str+link[x+dx[i]][y+dy[i]], x+dx[i], y+dy[i])
    }
  }
}

b2210()

알고리즘

• 재귀와 dfs를 사용하여 구한다.

1. "임의의 위치"에서 시작 -> 시작 점이 될 수 있는 점은 link[0][0] ~ link[4][4]이다.

1-1. 이중 for문으로 i=0 부터 i<5까지, j=0부터 j<5까지 재귀로 돌면서 탐색한다.

2. 이를 위한 재귀 함수를 만든다.

2-1. link의 x,y 좌표를 받는다.
2-2. x,y좌표에 해당하는 수를 toString()하여 str에 붙인다.
2-3. if (str의 길이가 6이 되면 && ans안에 str와 겹치는게 없으면) ans 배열에 넣고 return 한다.
2-4. x,y좌표를 이동시킨다.
※ 이때, 이동시키는 x,y의 범위가 0미만, 5이상으로 넘어가면 안된다.
그래서 dx=[1,-1,0,0], dy=[0,0,1,-1]을 만들어 준 것 !
👉🏻 현재 x,y좌표에서 인접한 정점으로 움직일 수 있는 점은 x좌표로 +1, -1 && y좌표로 +1, -1
👉🏻 움직일 수 있는 범위는 x-1 >= 0 && x+1 < 5 (y도 마찬가지)
👉🏻 따라서 이동할 수 있는 4가지 방향을 for 문으로 돌면서 범위 내에 있는 좌표로 재귀를 통해 이동한다.

3. link[4][4]까지 재귀를 돌면서 push한 ans의 길이를 출력한다.

백준에 나온 정답률에 비해선.. 어려웠다..
다시 보니까 이 문제를 시도한 사람들도 (다른 문제들에 비해선) 적었다. 그래서 정답률이 높게 나온건가?
dfs로 접근해야 한다는데 어떻게 접근하는게 좋을지, 특히 저 x,y 범위를 어떻게 해줘야 할지 막막했는데, 역시 구글신의 힘이란.. 코딩 고수님들의 힘이란..

또 한번 재귀 잘 배우고 갑니다 ㅠㅠ