[Softeer] HSAT 7회 정기 코딩 인증평가 기출 - 순서대로 방문(level3, Javascript)

✏️ 문제 링크

https://softeer.ai/practice/6246

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

✏️ 문제 풀이

백트래킹을 잘 익혀놓으면 쉬운 문제라고 생각한다. (백트래킹은 백준의 N과 M을 풀어보면 쉽게 익힐 수 있다. 꼭! ⭐️) 
코드가 좀 길긴하지만! 사실 뜯어보면 별거 없다.. 데이터 저장하는 코드 반,,,ㅠ 백트래킹 부분 반이다. 

내가 풀이한 코드의 방식은 

백트래킹으로 갈 수 있는 모든 경로를 탐색하고 그 안에서 우리가 원하는 순서를 지키는 path가 있을 때 answer를 ++ 하는 방식이다. 

 

1. 순서대로 방문을 해야한다고 했으니 순서대로 방문해야하는 위치의 index를 key, value로 저장해둔다. 

2. 현재 path의 시작과 끝이 start 와 end 와 동일하다면 그 안에 path를 체크한다. 

  2-1. path 안에서 만약 essential(순서 리스트)에 해당하는 위치가 있다면 count하고 그 count가 순서리스트의 순서와 동일한지 체크한다. 

3. 그게 아니라면 백트래킹으로 상하좌우 path 트래킹을 한다.

✏️ 문제 코드

const readline = require('readline');
const rl = readline.createInterface({input:process.stdin, output:process.stdout});


let input = [];
rl.on('line', function(line){
    input.push(line.split(' ').map(Number));
}).on('close', function(){
    const [n, m] = input.shift();
    const matrix = [];
    const essential = {};
    let start, end;
    
    for(let i=0; i<n; i++){
        matrix.push(input.shift());
    }
    for(let i=0; i<m; i++){
        const [x, y] = input[i];
        essential[`${x-1}+${y-1}`] = i+1;
        if(i===0) start = [x-1, y-1]; 
        if(i===m-1) end = [x-1, y-1];
    }

    const dx = [-1, 1, 0, 0]; const dy = [0, 0, -1, 1];
    const visited = Array.from(Array(n), ()=>Array(n).fill(false));
    let answer = 0;
    
    const search_path = (x, y, path) => {
        const [sx, sy ] = path[0]; const [ex, ey] = path[path.length-1];
        if(sx===start[0] && sy===start[1] && ex===end[0] && ey === end[1]){
            let cnt = 1;
            for(let i=1; i<path.length; i++){
                const [px, py] = path[i];
                const key = `${px}+${py}`
                if(essential[key]){
                    cnt++;
                    if(essential[key]===cnt)continue;
                    else return;
                }
            }
            answer++;
            return;
        }else{
            for(let i=0; i<4; i++){
                const nx = dx[i] + x; const ny = dy[i] + y;
                if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if(visited[nx][ny]===false && matrix[nx][ny]===0){
                    visited[nx][ny] = true;
                    search_path(nx, ny, [...path, [nx, ny]]);
                    visited[nx][ny] = false;
                }
            }
        }      
    } 
    
    visited[start[0]][start[1]] = true;
    search_path(start[0],start[1], [start]);
    
    console.log(answer);
    
})

 

 

 

 ⭐ if feedback and question : comment please⭐