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

(1).백준 21736번 헌내기는 친구가 필요해는 지도를 순회하며 만날 수 있는 사람의 숫자를 확인해야 하는 문제였다.

 

문제 자체는 이제 간단하게 해결할 수 있었지만

js라서 시간초과에 걸려버렸는데 이걸 위해 조금 더 최적화를 진행했지만 큰 의미는 없었다.

 

여기서 제일 큰 문제는 JS만의 shift 시간복잡도 문제였는데

이중연결리스트와는 다르게 배열에서는 시간복잡도가 n이 되어버리고

대기열은 최대 36만개까지 가기 때문에 방문 전 체크를 하고 경로를 한정한다고 해도 시간제한에 걸려버렸다.

 

문제를 해결하기위해 class로 리스트를 구현해야 하나 고민했는데

잘 생각해보니 최단 거리를 구하려는 문제가 아니고 존재 여부를 따지는 문제였기 때문에

dfs를 사용하면 간단히 해결할 수 있을 것 같았다.

 

물론 dfs를 사용할 경우 overflow가 생길 수 있지만

다행히 규모가 제한되어있기 때문에 dfs로 queue 대신 stack을 사용해 물제를 해결할 수 있었다.

let input = `3 5
OOOPO
OIOOX
OOOXP`.split('\n')
const [xLength, yLength] = input.shift().split(' ').map(Number)
input = input.map(el => el.split(''))
let count = 0
let xStart, yStart

for(let i = 0 ; i < xLength ; i++){
    for(let j = 0 ; j < yLength ; j++){
        if(input[i][j] === 'I'){
            xStart = i
            yStart = j
        }
    }
}
const stack = [[xStart, yStart]]

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

while(stack.length){
    const [x, y] = stack.pop()
    if(checker(x+1,y) && input[x+1][y] !== 'X'){
        if(input[x+1][y] === 'P') count++
        input[x+1][y] = 'X'
        stack.push([x+1,y])
    }
    if(checker(x-1,y) && input[x-1][y] !== 'X'){
        if(input[x-1][y] === 'P') count++
        input[x-1][y] = 'X'
        stack.push([x-1,y])
    }
    if(checker(x,y+1) && input[x][y+1] !== 'X'){
        if(input[x][y+1] === 'P') count++
        input[x][y+1] = 'X'
        stack.push([x,y+1])
    }
    if(checker(x,y-1) && input[x][y-1] !== 'X'){
        if(input[x][y-1] === 'P') count++
        input[x][y-1] = 'X'
        stack.push([x,y-1])
    }
}

console.log(count > 0 ? count : 'TT')