[개발일지] - 23(주말)

(1).백준 14940번 쉬운 최단거리는 이름과는 다르게 완전 기초는 아니었고

BFS를 아는지 묻는 문제였다.

 

오랬만에 bfs문제를 보니 잠깐 당황했지만

상식적으로 거리를 한칸씩 순차적으로 탐색하려면 queue를 써야 하는게 금방 떠올랐고

예전에 쓰는 [[-1,0], [1,0], [0,-1], [0, 1]]형태로 4좌표값 비교도 쓰고 싶었는데

그건 다음에 기회되면 사용하기로 하고

방향을 체크하는 함수만 추가해서 만들었다.

 

예전에는 에러가 터지지 않도록 arr[x] && arr[y] && map[x][y] === 1 뭐 이런 형식으로

배열 앞부분 체크를 먼저 진행했었는데

이번에는 x,y좌표값을 먼저 던져서 유효한지 체크하는걸 만드니 조금 더 깔끔해 보였다.

 

input을 기존 지도로 삼고 map을 이동해야 하는 거리 표기용으로 만든 다음

현재 출발지점인 2의 위치를 기록하고 queue에 해당 위치를 넣은 다음

queue가 존재하는 동안 while문을 돌아가게 만들었는데

내부 변수의 이름이 조금 아쉬웠다.

 

최종적으로 제출하고 틀려서 당황했는데

문제를 자세히 읽어보니 원래 갈 수 있는데 못가는 이상한 명칭의 도로는 -1로 표기해야 한다고 하는데

해당 예제가 없어서 뭔가 싶었지만

input에 1로 남아있던 값들을 의미한다는 사실을 알고나니

마지막에 이중 for문을 통해 해당 좌표값을 -1로 바꾸니 통과할 수 있었다.

const input = `15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1`.split('\n').map(el => el.split(' ').map(Number))
const [xLength, yLength] = input.shift()
const map = []
let x,y
for(let i = 0 ; i < xLength ; i++){
    map.push(new Array(yLength).fill(0))
    for(let j = 0 ; j < yLength ; j++){
        if(input[i][j] === 2){
            x = i
            y = j
        }
    }
}
const queue = [[x,y]]

const check = (x, y) => {
    if(0 <= x && x < xLength && 0 <= y && y < yLength){
        return true 
    }
    return false
}

while (queue.length) {
    const [xNow, yNow] = queue.shift()
    if(check(xNow+1,yNow) && input[xNow+1][yNow] === 1){
        input[xNow+1][yNow] = 0
        map[xNow+1][yNow] = map[xNow][yNow] + 1
        queue.push([xNow+1,yNow])
    }
    if(check(xNow-1,yNow) && input[xNow-1][yNow] === 1){
        input[xNow-1][yNow] = 0
        map[xNow-1][yNow] = map[xNow][yNow] + 1
        queue.push([xNow-1,yNow])
    }
    if(check(xNow,yNow+1) && input[xNow][yNow+1] === 1){
        input[xNow][yNow+1] = 0
        map[xNow][yNow+1] = map[xNow][yNow] + 1
        queue.push([xNow,yNow+1])
    }
    if(check(xNow,yNow-1) && input[xNow][yNow-1] === 1){
        input[xNow][yNow-1] = 0
        map[xNow][yNow-1] = map[xNow][yNow] + 1
        queue.push([xNow,yNow-1])
    }
}

for(let i = 0 ; i < xLength ; i++){
    for(let j = 0 ; j < yLength ; j++){
        if(input[i][j] === 1){
            map[i][j] = -1
        }
    }
}
console.log(map.map(el => el.join(' ')).join('\n'))