백준 2210: 숫자판 점프 - javascript (dfs)

문제 출처 

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

2210번: 숫자판 점프

문제

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 이 가능한 경우들이다.

 

문제 풀이 힌트 

문제가 이해가 갔나요? 저는 처음에 뭔 말이지 싶었는데요 

그래프에 적혀있는 숫자들로 6자리 수를 만들어라! 단, 그래프에서 사방면으로 움직이면서 만들어라 !

 이렇게 움직이면 121111 이 된다. 

이렇게 움직이면 121112가 된다 (중복해서 방문해도 되니까 )

문제를 구성해봅시다 !

- 이중 반복문을 이용해서 그래프의 모든 위치를 시작점으로 설정한다. 

- dfs를 활용해서 사방면으로 갈 수 있도록 한다. 

- 문자 길이가 6가 되었을 때 numbers 배열에 push 한다. 

- new Set 을 이용해서 배열 속 중복된 숫자는 빼준다 . 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const graph = input.map(v => v.split(' ').map(Number)); 
const ds = [[0,1],[0,-1],[1,0],[-1,0]];
let numbers = []; 
function dfs(x,y,str){
    if(str.length === 6){
       numbers.push(str); 
    }else{
        for(let i=0; i<4; i++){
            let nx = x + ds[i][0]; 
            let ny = y + ds[i][1]; 
            if(nx < 0 || ny < 0 || nx >=5 || ny >= 5) continue; 
            else{
              dfs(nx, ny, str + graph[nx][ny]);    
            }
        }    
    }
}
for(let i=0; i<5; i++){
    for(let j=0; j<5; j++){
        dfs(i,j,''); 
    }
}
console.log([...new Set(numbers)].length);

의사 코드 추가 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const graph = input.map(v => v.split(' ').map(Number)); 
const ds = [[0,1],[0,-1],[1,0],[-1,0]]; //사방면 움직이기 위함
let numbers = []; 
function dfs(x,y,str){
    if(str.length === 6){
       numbers.push(str); 
    }else{
        for(let i=0; i<4; i++){ //사방면 움직이기 
            let nx = x + ds[i][0]; 
            let ny = y + ds[i][1]; 
            if(nx < 0 || ny < 0 || nx >=5 || ny >= 5) continue; // 그래프에서 벗어나는 위치 제낀다.  
            else{
              dfs(nx, ny, str + graph[nx][ny]); //다음 위치, 문자로 추가     
            }
        }    
    }
}
// 시작점은 그래프의 모든 위치가 되어야 한다. 
for(let i=0; i<5; i++){
    for(let j=0; j<5; j++){
        dfs(i,j,''); 
    }
}
console.log([...new Set(numbers)].length); //numbers 배열중 중복되는거 빼기