[JS] 아이템 줍기

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

프로그래머스

 

 

처음에 문제접근을 잘못해서 두번 해결한 문제였다.

 

처음에는 도화지위에 네모 모양의 성벽을 쌓은 이후, 밖에서 물을 부으면 성벽을 기준으로 바깥쪽만 물의 영역이 되는 원리를 이용해서 문제를 해결하려고 했다.

 

(비록 문제에서는 직사각형이 4개뿐이지만 위 방법을 사용하면 직사각형의개수가 매우많아져도 시간복잡도에 크게 영향이 없기 떄문)

 

 

 

 

 

 

해당방법으로 구현은 했지만 위처럼 ㄷ자로 이어지는 성벽을 구현하지 못했다...

 

문제를 접근할때 한 점을 벽이라고 생각하면 안된다. 문제는 점과점을 잇는 선분!!! 이므로 한 점에서 다른 점으로 이동하는 경로 즉 그래프의 관점에서 봤어야 했다.

 

따라서 썼던 코드를 다 지우고

 

사각형이 4개밖에 안되므로 4각형을 2차원 배열위에 그리는 경우에 해당 선분이 다른 직사각형 내부에 있는지 확인하여 만약 있지 않다면 최외각 둘레라고 생각하면서 최외각 거리를 구한 이후, bfs와 그래프를 활용해서 최소 거리를 구해주면 된다.

 

 

 

문제에 접근방식 자체는 따라서 간단하다.

 

1. 최외각 테두리 구하기

2. bfs로 최외각 테두리를 따라가며 최소거리 반환

 

 

1번 배열을 구하기 위한 방법은 아래와 같다.

1.최외각 테두리를 구하기 위해서 각 점에서 다른점으로 가는지 여부 즉 선분의 정보를 저장할 graph 배열을 생성

2.사각형의 모든 선분들을 검사하며 다른 사각형 내부에 해당 선분이 없다면 graph배열에 push

 

 

function solution(rectangle, characterX, characterY, itemX, itemY) {
    
   const graph = [...Array(51)].map(_ => [...Array(51)].map(__ => []))
   
   //해당 선분이 다른 사각형 안에 있는지 확인
   const isLineInOtherBox = (idx,aY,aX,bY,bX) => {
           for (let i = 0 ; i < rectangle.length ; i++){
               if(i===idx ) continue
               const [lx,ly,rx,ry] = rectangle[i]
               if(lx<=aX && aX<=rx && lx<=bX && bX<=rx &&ly<=aY&&aY<=ry&&ly<=bY&&bY<=ry)
               return true
           }
           return false
   }
   
   
   for ( let idx = 0 ; idx < rectangle.length ; idx ++){
       const [lx,ly,rx,ry] = rectangle[idx]
       //좌->우 상->하 방향으로 선분들이 다른 사각형 내부에 있는지 검사
       for (let i = lx ; i < rx ; i++){
           if (!isLineInOtherBox(idx,ry,i,ry,i+1)) {
               graph[ry][i].push([ry,i+1])
               graph[ry][i+1].push([ry,i])
           }
           if (!isLineInOtherBox(idx,ly,i,ly,i+1)) {
               graph[ly][i].push([ly,i+1])
               graph[ly][i+1].push([ly,i])
           }
       }
       for (let i = ly ; i < ry ; i++){
           if (!isLineInOtherBox(idx,i,lx,i+1,lx)) {
               graph[i][lx].push([i+1,lx])
               graph[i+1][lx].push([i,lx])
           }
           if (!isLineInOtherBox(idx,i,rx,i+1,rx)) {
               graph[i][rx].push([i+1,rx])
               graph[i+1][rx].push([i,rx])
           }
       }
   }

    //que를 활용한 bfs로 최소거리가 감지되면 더이상 탐색을 하지않게끔
    const visited = [...Array(51)].map(_ => Array(51).fill(false))
    const que = [[characterY,characterX,0]]
    let queIdx = 0
    visited[characterY][characterX] = true
    
    while (queIdx < que.length){
        const [y,x,cnt] = que[queIdx]
        if(y===itemY && x === itemX) return cnt
        visited[y][x] = true
        
        for (const [ny,nx] of graph[y][x]){
            if(!visited[ny][nx]) que.push([ny,nx,cnt+1])
        }
        queIdx ++
    }
    
    
    
}