[프로그래머스][bfs] 리코쳇 로봇 bfs 구현

     

목차

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

 

문제 구현 방향

처음에 백트래킹으로 풀어서 삽질했다.. 시간 초과가 난다. (최악의 경우 4가지 분기를 100*100승 하는데 당연한건데 시간 복잡도 고려가 부족했다.)

bfs로 다시 푸니 금방 해결했다. (O(V+E) 이므로 10000 + 4*10000  = 50000)

 

 

백트래킹으로 구현

let dr = [[1,0], [-1,0], [0, 1], [0, -1]];
var answer = Infinity;

function solution(board) {
    let m = [];
    let startY =0;
    let startX =0;
    let y =0;
    let cnt =1;
    for(let b of board){
        let split = b.split("");
        for(let idx=0; idx< split.length; idx++){
            if(split[idx] === 'R'){
                startX = idx;
                startY = y;
            }
               
        }
        y++;
        m.push(split);
    }
    let visit = Array.from({length: 101}, ()=> Array(101).fill(0));
    
    backtracking(startX, startY, visit, m, cnt);
    
    
    return isFinite(answer) ? answer:-1;
}

function backtracking(x, y, visit, m, cnt){
    if(cnt >= answer)return;
    let col = m[0].length;
    let row = m.length;
    
    for(let k of dr){
        let nx = x;
        let ny = y;
        while(true){
            if(nx < 0 || nx >col-1 || ny < 0 || ny > row-1 || m[ny][nx] === 'D') break;
            nx += k[0];
            ny += k[1];
        }
        let tx = nx - k[0];
        let ty = ny - k[1];
        if(visit[ty][tx]) continue;
        if(m[ty][tx] === 'G') {answer = Math.min(cnt, answer);
                              return;}
        
        visit[ty][tx] = 1;
        backtracking(tx, ty, visit, m, cnt+1);
        visit[ty][tx] = 0;

    }
    
}

 

 

bfs로 구현

let dr = [[1,0], [-1,0], [0, 1], [0, -1]];
var answer = Infinity;

function solution(board) {
    let m = [];
    let startY =0;
    let startX =0;
    let y =0;
    let cnt =1;
    for(let b of board){
        let split = b.split("");
        for(let idx=0; idx< split.length; idx++){
            if(split[idx] === 'R'){
                startX = idx;
                startY = y;
            }
               
        }
        y++;
        m.push(split);
    }
    
    let visit = Array.from({length: 101}, ()=> Array(101).fill(0));

    bfs(startX, startY, m, visit);
    return isFinite(answer) ? answer:-1;
}

function bfs(startX, startY, board, visit){
    
    let queue = [];
    let col = board[0].length;
    let row = board.length;
    
    queue.push([startX, startY]);
    visit[startY][startX] = 1;
    
    while(queue.length){
        let [x, y] = queue.shift();
        for(let k of dr){
            let nx = x;
            let ny = y;
        while(true){
            if(nx < 0 || nx > col-1 || ny < 0 || ny > row-1 || board[ny][nx] === 'D' )break;
            nx += k[0];
            ny += k[1];
        }
        let tx = nx - k[0];
        let ty = ny - k[1];
        if(visit[ty][tx]) continue;
        cnt++;
        visit[ty][tx] = visit[y][x] + 1;
        if(board[ty][tx] === 'G') answer = Math.min(answer, visit[ty][tx]-1);
        queue.push([tx, ty]);
        
        }
        
    }
    
}