[Programmers] 아이템 줍기 문제 - (javascript)

문제 이름 :  아이템 줍기

---

 

<<< 문제 내용 >>>

---

 

function solution(rectangle, characterX, characterY, itemX, itemY) {
    let answer = [];
    let board = Array.from(Array(101), () => new Array(101).fill(0));
    
    rectangle.forEach((el, i)=>{
        const yStart = el[1]*2;
        const yEnd = el[3]*2;
        const xStart = el[0]*2;
        const xEnd = el[2]*2;
        
        for(let y=yStart; y<=yEnd; y++){
            for(let x=xStart; x<=xEnd; x++){
                if(y===yStart || y===yEnd || x===xStart || x===xEnd){
                    if(board[y][x] === 1) continue;
                    else board[y][x] += 1
                }
                else board[y][x] = 2;
            }
        }
    });
    
    
    const dy = [-1,1,0,0];
    const dx = [0,0,-1,1];
    
    const bfs = (y, x, cnt) => {
        let queue = [[y, x, cnt]];
        let visited = Array.from(Array(101), () => new Array(101).fill(false));
        
        while(queue.length){
            [y, x, cnt] = queue.shift();
            visited[y][x] = true;
            
            if(y === itemY*2 && x === itemX*2) return cnt/2;
            
            for(let i=0; i<4 ;i++){
                let ny = y + dy[i];
                let nx = x + dx[i];
                
                if(ny<0||ny>=101||nx<0||nx>=101) continue;
                
                if(!visited[ny][nx] && board[ny][nx] === 1){
                    queue.push([ny, nx, cnt+1]);
                }
            }
        }
    }
    
    return bfs(characterY*2, characterX*2, 0);
}

* 굉장히 스트레스 받는 문제였다...

이 문제를 풀면서 어이가 없었기 때문에 평소와 다르게 오늘은 일기처럼 써볼까 한다.

 

처음엔 생각보다 빠르게 테두리를 다 그리고, 내부를 비우고 bfs로 찾아가면 되겠다는 결론을 세웠다.

 

뭔가 잘 될거 같다는 마음으로 코딩을 다 하고나서 확인했더니 엥? 테케 1, 5 번이 오류가 났다.

 

콘솔로 이동 방향을 찍어보니..

 

이때 4방향 탐색을하면서 아주 그냥 널뛰기를 해버린다.

 

이를 해결하기 위해, 각 꼭지점을 구분해놓고, 꼭지점에서 갑자기 똑같은 방향으로 질러가면

그 방향은 처리되지 않게 끔 하려고 했다.

 

근데 고민해보니, 첫 시작이 꼭지점일때 구현이 굉장히 어려웠다.

 

어떡하지 고민하다가 그림이 좌표여서 얻은 힌트인 "전체 도형을 2배로 늘리면 되겠다!" 라는 생각을 했다.

( 좌표 그림이 아니었다면 아마 못 떠올렸을 듯 )

 

내가 생각하고도 놀랬는데, 나중에 어떤 오류때문에 질문하기를 눌렀다가 이게 대표적인 해결법이라는 것도 깨달았다.

 

아무튼 정상적으로 작성 후, 테스트케이스가 전부 맞았다.

 

기쁜 마음으로 제출했는데 웬걸? 55점? 중간에 런타임에러를 보고 아~ 지도를 2배로 안키웠네 싶었다.

2배로 키우고.. 어? 또 55점이다.

 

진짜 한참을 끙끙거렸다. 다 2배로 잘 한거 같았고, 계속 코드를 보다가

bfs의 테두리 밖으로 나가는 예외처리를 50칸으로 두고 고치지 않았던 것이다.

 

결국 내 실수로 시간을 오래 쓴 징징 일기였다.. 어쨋든 풀어서 만족스럽긴 하다😀

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.