Portfolio

문제

풀이

은찬


const checkRange = (x, y) => (x >= 0 && x < 5 && y >= 0 && y < 5);

const dfs = (place) => {
    for(let x = 0; x < 5; x++){
        for(let y = 0; y < 5; y++){
            if(place[x][y] === "P"){
                if(!(checkStraight1(x, y, place) && checkStraight2(x, y, place) && checkDiagonal(x, y, place))){
                    return false;
                }
            }
        }
    }
    
    return true;
}

const checkStraight1 = (x, y, place) => {
    const straightX = [-1, 1, 0, 0];
    const straightY = [0, 0, -1, 1];
    
    for(let i = 0; i < 4; i++){
        const nx = x + straightX[i];
        const ny = y + straightY[i];
        
        if(checkRange(nx, ny)){
            if(place[nx][ny] === "P"){
                return false;
            }
        }
    }
    
    return true;
}

const checkStraight2 = (x, y, place) => {
    const straightX = [-2, 2, 0, 0];
    const straightY = [0, 0, -2, 2];
    const partitionX = [-1, 1, 0, 0];
    const partitionY = [0, 0, -1, 1];
    
    for(let i = 0; i < 4; i++){
        const nx = x + straightX[i];
        const ny = y + straightY[i];
        const px = x + partitionX[i];
        const py = y + partitionY[i];
        
        if(checkRange(nx, ny)){
            if(place[nx][ny] === "P" && place[px][py] !== "X"){
                return false;
            }
        }
    }
    
    return true;
}

const checkDiagonal = (x, y, place) => {
    const diagonalX = [-1, 1, 1, -1];
    const diagonalY = [1, 1, -1, -1];
    const partitionX = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    const partitionY = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    for(let i = 0; i < 4; i++){
        const nx = x + diagonalX[i];
        const ny = y + diagonalY[i];
        const px1 = x + partitionX[i][0];
        const px2 = x + partitionX[i][1];
        const py1 = y + partitionY[i][0];
        const py2 = y + partitionY[i][1];
        
        if(checkRange(nx, ny)){
            if(place[nx][ny] === "P" && (place[px1][py1] !== "X" || place[px2][py2] !== "X")){
                return false;
            }
        }
    }
    
    return true;
}


const solution = (places) => {
    const answer = [];
    
    for(let i = 0; i < 5; i++){
        answer.push(dfs(places[i]) ? 1 : 0);
    }
    return answer;
}

효성

첫 번째 풀이 - `실패`

본질은 p와 p가 만나지 않는 건데 이를 선택하기 보단 모든 경우를 생각해내려고 함.

근데 모든 경우를 생각해내지 못함 ex) 대각선에 p가 있을 때 파티션 차단 여부 체크.


function solution(places) {
    const answer = [];
    const boards = Array.from(Array(5), () => new Array(5));
    for(let i=0; i<5; i++) {
        for(let j=0; j<5; j++) {
            boards[i][j] = places[i][j].split('');
        }
    }
    boards.forEach(board => {
        for(let i=0; i<5; i++) {
            for(let j=0; j<5; j++) {
                if(board[i][j] === 'P') {
                    if(!canSit(i, j, board)) {
                        answer.push(0);
                        break;
                    }
                }
            }
            answer.push(1);
        }
    });   
    console.log(answer)
}

function canSit(x, y, arr) {
    const firstDirX = [-1, 1, 0, 0], firstDirY = [0, 0, -1, 1];
    const secondDirX = [-2, 2, 0, 0], secondDirY = [0, 0, -2, 2];
    const crossDirX = [-1, 1, -1, 1], crossDirY = [-1, 1, -1, 1];
    
    for(let i=0; i<4; i++) {
        const fx = x + firstDirX[i], fy = y + firstDirY[i];
        const sx = x + secondDirX[i], sy = y + secondDirY[i];
        
        if(isValidPos(fx, fy) && arr[fx][fy] === 'P') {
            return false;
        }
        if(isValidPos(fx, fy) && arr[fx][fy] === 'O') {
            if(isValidPos(sx, sy) && arr[sx][sy] === 'P') {
                return false;
            }
        }
        
    }
    return true;
}

function isValidPos(row, col) {
    return row >= 0 && row < 4 && col >= 0 && col < 4;
}

참고한 풀이

본질은 p가 2칸 안에 다른 p를 만나면 안된다는 것.


function solution(places) {
    return places.map(place => isValidPlace(place) ? 1 : 0)
}

function isValidPlace(place) {
    const dr = [0, 0, -1, 1];
    const dc = [1, -1, 0, 0];
    let isValid = true;
    
    const dfs = (r, c, depth, visit) => {
        if(depth >= 2) return;
        
        visit[r][c] = true;
        for(let i = 0; i < 4; i++) {
            const nr = dr[i] + r;
            const nc = dc[i] + c;
            if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
            if(visit[nr][nc]) continue;
            if(place[nr][nc] === "X") continue;
            if(place[nr][nc] === "P") isValid = false;
            visit[nr][nc] = true;
            dfs(nr, nc, depth + 1, visit);
        }
    }
    
    for(let r = 0; r < 5; r++) {
        for(let c = 0; c < 5; c++) {
            if(place[r][c] !== "P") continue;
            const visit = [...Array(5)].map(_ => [...Array(5)].fill(false));
            isValid = true;
            dfs(r, c, 0, visit);
            if(!isValid) return false;
        }
    }
    
    return true;
}

거리두기 확인하기

문제

풀이

첫 번째 풀이 - 실패

참고한 풀이

첫 번째 풀이 - `실패`