[취업준비일지] - 141

SCSA 지원 자격을 위한 토익스피킹을 일요일에 치기 때문에

부랴부랴 2일만에 첫 토익스피킹 준비를 하고 있다.

 

(1).백준 7576번 토마토는 날짜의 흐름을 구해야 하는 문제였다.
BFS를 통해 모든 내용을 처리한 다음 제일 큰 숫자를 구해도 되겠지만
BFS로 처리할 경우 모든 연산을 shift로 처리해야 했는데 시간복잡도가 높아졌다.

그렇다고 DFS로 하려고 하면 (?) 지금 생각해보니 가능한 것이 있었다.
어쨌든 문제를 풀 당시에는 DFS로 하면 날자 처리가 꼬이기 때문에
pop을 사용할 수는 없었고
(0을 1억 등의 숫자로 세팅해준 다음 Math.min을 통해 처리해도 될 것 같다)

날짜의 경과를 어떻게 처리해야 할지 고민하다가
이중 while문을 통해 더 이상 처리할 작업이 없을 때 까지 진행하고
각각의 다음 이동은 newStack에 담은 다음
stack을 비운 후 newStack의 길이를 체크해
작업이 추가로 필요하면 stack에 newStack을 구조분해할당으로 할당해주고
day를 증가시켰다.

newStack이 존재하지 않는 경우 다음날이 필요하지 않다고 판단했기 때문에
그대로 작업을 종료시켰고
최종적으로 0이 하나라도 남아있다면 장애물에 막혀 처리되지 못한다고 보고
-1을 출력했다.

const input = `5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0`.split('\n')

const map = []
let day = 0
for(let i = 1 ; i < input.length ; i++){
    map.push([...input[i].split(' ').map(Number)])
}

let stack = []

for(let i = 0 ; i < map.length ; i++){
    for(let j = 0 ; j < map[0].length ; j++){
        if(map[i][j] > 0){
            stack.push([i,j])
        }
    }
}

while(true){
    const newStack = []
    while(stack.length){
        const [x, y] = stack.pop()
        if(map[x+1] && map[x+1][y] === 0){
            map[x+1][y] = 1
            newStack.push([x+1,y])
        }
        if(map[x-1] && map[x-1][y] === 0){
            map[x-1][y] = 1
            newStack.push([x-1,y])
        }
        if(map[x][y+1] === 0){
            map[x][y+1] = 1
            newStack.push([x,y+1])
        }
        if(map[x][y-1] === 0){
            map[x][y-1] = 1
            newStack.push([x,y-1])
        }
    }
    if(newStack.length){
        day++
        stack = [...newStack]
    }
    else{
        break
    } 
}

for(let i = 0 ; i < map.length ; i++){
    if(map[i].filter(el => el === 0).length){
        day = -1
    }
}

console.log(day)