작성한 질문수 5

1

수십회 시도 끝에 겨우 통과되었습니다. 별거 아닌데 진짜 시간초과가 너무 타이트 하네요.

• 내부 함수에서 지역 변수 대신 글로벌 변수 사용

• 큐에서 꺼낼 때 shift() 대신 index 로 접근

https://www.acmicpc.net/source/share/cd8df7c6f13f4ed8a9114901672d3f70

1

안녕하세요 ㅎㅎ

C++외의 코드는 봐드리지 않습니다.

다만 어느정도는 주석을 달아드렸습니다. 참고해주세요.

const filePath = '/dev/stdin';
const input = require('fs')
    .readFileSync(filePath)
    .toString()
    .split('\n');
const [row, col] = input[0].split(' ').map(Number);
console.log(solution(row, col, input.slice(1).map(v => v.split(''))));
function solution(r, c, grid) {
    //good
    const distance = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    const visitedSwan = Array.from({ length: r }, (v => new Array(c).fill(0)));
    const visitedIce = Array.from({ length: r }, (v => new Array(c).fill(0)));
    let ices = [];
    let swans = [];
    //some을 이용한 사례 : good
    //isAroundWall : 이라면  grid[ny][nx] === 'X' 이 들어가면 안됩니다. 
    // 그냥 범위 벗어나는지 안되는 지만 확인하는게 좋아요. 
    const isAroundWall = (y, x) => {
        return distance.some(([dy, dx]) => {
            const ny = dy + y;
            const nx = dx + x;
            return (ny in grid && nx in grid[0] && grid[ny][nx] === 'X')
        })
    }
    for (let i = 0; i < r; i ++) {
        for (let j = 0; j < c; j ++) {
            if (grid[i][j] === 'L' && !swans.length) {
                visitedSwan[i][j] = 1;
                swans.push([i, j])
                //물일 때 집어넣는 것. 
            } else if (grid[i][j] !== 'X') {
                visitedIce[i][j] = 1; 
                //이걸 왜 체크하는 거죠? 범위벗어나는 것을 확인할 필요는 없죠.
                // 입력에서 하는건데요.
                if (isAroundWall(i, j)) {
                    ices.push([i, j]);
                }
                
            }
        }
    }
    const meltIce = (ices, grid, visited) => {
        let nextIces = [];
        while (ices.length) {
            const [y, x] = ices.shift();
            for (let [dy, dx] of distance) {
                const ny = y + dy;
                const nx = x + dx;
                if (!(ny in grid) || !(nx in grid[0]) || visited[ny][nx]) continue;
                visited[ny][nx] = 1;
                if (grid[ny][nx] === 'X') {
                    grid[ny][nx] = '.';
                    nextIces.push([ny, nx]);
                }
            }
        }
        return nextIces;
    }
    const moveSwan = (swans, grid, visited) => {
        const nextSwans = [];
        while (swans.length) {
            const [y, x] = swans.shift();
            for (let [dy, dx] of distance) {
                const ny = y + dy;
                const nx = x + dx;
                if (!(ny in grid) || !(nx in grid[0]) || visited[ny][nx]) continue;
                visited[ny][nx] = 1;
                if (grid[ny][nx] === 'L') return [];
                if (grid[ny][nx] === '.') {
                    swans.push([ny, nx]);
                } else {
                    nextSwans.push([ny, nx]);
                }
            }
        }
        return nextSwans;
    }
    let count = 0;
    // 저는 bool 변수 isSwanMeet를 기반으로 while문을 돌렸는데요. 
    // 이러한 부분 등이 다른 것 같습니다. 
    while (swans.length) {
        swans = moveSwan(swans, grid, visitedSwan);
        if (!swans.length) break;
        ices = meltIce(ices, grid, visitedIce);
        count++;
    }
    return count;
}

또한, 이 백조의 호수는 C++로 구현해도 시간초과가 많이 발생하는 시간초과가 타이트한 문제임을 참고해주세요. 그렇기 때문에 TC가 맞으면 넘어가도 되는 수준의 문제입니다.

감사합니다.