프로그래머스 [Lv. 3] 퍼즐 조각 채우기 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/84021

프로그래머스

정답 코드

function solution(game_board, table) {
    let answer = 0;
    // 체크 맵
    let checkMap = new Map();
    const setMap = (key) => {
        if (checkMap.has(key)) {
            checkMap.set(key, checkMap.get(key)+1);
        } else {
            checkMap.set(key, 1);
        }
    }
    
    // 길이
    const n = game_board.length;
    
    // 방향 범위
    const dr = [-1, 1, 0, 0, -1, -1, 1, 1];
    const dc = [0, 0, -1, 1, 1, -1, 1, -1];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < n;
    };
    const eightDirections = (arr, visited, lenA) => {
        const newArr = [];
        for (const [r, c] of arr) {
            let straight = 0;
            let left = 0;
            let right = 0;
            // 0 ~ 3는 같은 방향으로 취급하고 
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && visited[nr][nc]) {
                    straight++;
                }
            }
            // 4 ~ 7은 꺾이는 지점으로 한다.
            for (let d = 4; d < 8; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && visited[nr][nc]) {
                    // 오른쪽
                    // 같은 행에 정사각형이 있고
                    if (visited[r][nc]) {
                        // 오른쪽에 있으며
                        if (c < nc) {
                            // 행이 작은 경우 왼쪽
                            if (r > nr) {
                                left++;
                            } else {
                                right++;
                            }
                        } else {
                            // 왼쪽에 있으며
                            // 행이 작은 경우 오른쪽
                            if (r > nr) {
                                right++;
                            } else {
                                left++;
                            }
                        }
                    }
                    // 왼쪽
                    // 같은 열에 정사각형이 있고
                    if (visited[nr][c]) {
                        // 위에 있고
                        if (r > nr) {
                            // 열이 크면 오른쪽
                            if (c < nc) {
                                right++;
                            } else {
                                left++;
                            }
                        } else {
                            // 아래에 있고
                            // 열이 크면 왼쪽
                            if (c < nc) {
                                left++;
                            } else {
                                right++;
                            }
                        }
                    }
                }
            }
            newArr.push([straight, left, right]);
        }
        
        newArr.sort(([a, b, c], [d, e, f]) => a - d || b - e || c - f);
        return newArr;
    }
    
    // bfs
    const bfs = (sr, sc, isBlock) => {
        const deque = [[sr, sc]];
        const rows = new Map();
        const cols = new Map();
        rows.set(sr, 1);
        cols.set(sc, 1);
        // 8방향 확인을 위한 visited
        const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));
        visited[sr][sc] = true;
        const keys = [[sr, sc]];
        
        if (isBlock) {
            table[sr][sc] = 0; // 빈칸 채워서 더 못찾게 하기
        } else {
            game_board[sr][sc] = 1; // 빈칸 채워서 더 못찾게 하기
        }
        
        let count = 1;
        while (deque.length > 0) {
            const [r, c] = deque.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                let isTrue = false;
                if (isValid(nr, nc)) {
                    if (isBlock && table[nr][nc] === 1) {
                        table[nr][nc] = 0;
                        isTrue = true;
                    } else if (!isBlock && game_board[nr][nc] === 0) {
                        game_board[nr][nc] = 1;
                        isTrue = true;
                    }
                }
                if (isTrue) {
                    deque.push([nr, nc]);
                    keys.push([nr, nc]);
                    visited[nr][nc] = true;
                    count++;
                    if (rows.has(nr)) {
                        rows.set(nr, rows.get(nr)+1);
                    } else {
                        rows.set(nr, 1);
                    }
                    if (cols.has(nc)) {
                        cols.set(nc, cols.get(nc)+1);
                    } else {
                        cols.set(nc, 1);
                    }
                }
            }
        }
        
        const cnt = keys.length;
        keys.sort(([a, b], [c, d]) => a - c || d - b);
        const newKeys = eightDirections(keys, visited, cnt);
        
        // 행 키
        const rowsEntries = [...(rows.entries())].map((e) => e);
        rowsEntries.sort(([a, b], [c, e]) => a - c);
        const rowsKeys = rowsEntries.map((e) => e[1]);
        // 열 키
        const colsEntries = [...(cols.entries())].map((e) => e);
        colsEntries.sort(([a, b], [c, e]) => a - c);
        const colsKeys = colsEntries.map((e) => e[1]);
        
        const cr = [...colsKeys].reverse();
        const rr = [...rowsKeys].reverse();
        
        const firstKey = `${count}-${rowsKeys}-${colsKeys}-${newKeys}`;
        const secondKey = `${count}-${cr}-${rowsKeys}-${newKeys}`;
        
        const thirdKey = `${count}-${rr}-${cr}-${newKeys}`; 
        const fourthKey = `${count}-${colsKeys}-${rr}-${newKeys}`;

        // set에 넣어야 함
        const set = new Set([firstKey, secondKey, thirdKey, fourthKey]);
        // 블럭이면 확인하고 있으면 둘 다 -1 
        if (isBlock) {
            // key 둘 중에 하나는 있을 것이다.
            if (checkMap.has(firstKey)) {
                if (checkMap.get(firstKey) > 0) {
                    // 둘 중 하나만 탐색해도 있겠지만 둘 다 지워야 한다.
                    for (const sv of set) {
                        checkMap.set(sv, checkMap.get(sv)-1);
                    }
                    // answer에 count만큼 저장
                    answer += count;
                }
            } 
        } else {
            // 빈칸을 체크맵에 저장
            for (const sv of set) {
                setMap(sv);
            };
        }
    }
    
    // 빈칸 먼저 저장하고
    for (let sr = 0; sr < n; sr++) {
        for (let sc = 0; sc < n; sc++) {
            if (game_board[sr][sc] === 0) {
                bfs(sr, sc, false);
            }
        }
    }
    
    // 블록으로 빈칸에 넣을 수 있는지 확인
    for (let sr = 0; sr < n; sr++) {
        for (let sc = 0; sc < n; sc++) {
            if (table[sr][sc] === 1) {
                bfs(sr, sc, true);
            }
        }
    }
    return answer;
}

풀이 방법

• 방향 탐색은 다들 할 줄 아니 생략하고 map을 왜 사용했는지 적어보려고 한다.
• rows와 cols는 무엇인가
  • 빈칸이나 블록을 찾으면 [[1, 2], [3, 4], [5, 6], [nr, nc]] 이런식으로 저장이 된다.
  • 여기에 해당하는 행 index는 rows에 키 값으로 들어가고 이후에 같은 행 index가 나오면 +1을 해준다.
  • 열도 마찬가지로 해준다.
  • 그 후 [key, value] 형태를 요소로 가지는 배열을 만든다.
    • const rowsEntries = [...(rows.entries())].map((e) => e);
    • 그리고 정렬 하는데 key값을 기준으로 오름차순 정렬한다.
    • rowsEntries.sort(([a, b], [c, e]) => a - c);
    • 그 후 value로 된 배열을 새로 만든다.
    • const rowsKeys = rowsEntries.map((e) => e[1]);
    • 열도 마찬가지
  • 예를 들어
    • game_board = [[0, 0, 0], [0, 1, 1], [1, 1, 1]]일 때
    • rows = [3, 1]
    • cols = [2, 1, 1]

배열	[[0, 0, 0], [0, 1, 1], [1, 1, 1]]	[[1, 1, 0], [0, 0, 0], [1, 1, 1]]	[[1, 0, 0], [1, 1, 0], [1, 1, 0]]	[[0, 1, 1], [0, 1, 1], [0, 0, 1]]
[[0, 0, 0], [0, 1, 1], [1, 1, 1]]	rows: [3, 1] cols: [2, 1, 1]	rows: rows.reverse() cols: cols.reverse()	rows: cols cols: rows.reverse()	rows: cols.reverse() cols: rows
[[1, 1, 0], [0, 0, 0], [1, 1, 1]]	rows: rows.reverse() cols: cols.reverse()	rows: [1, 3] cols: [1, 1, 2]	rows: cols.reverse() cols: rows	rows: cols cols: rows.reverse()
[[1, 0, 0], [1, 1, 0], [1, 1, 0]]	rows: cols cols: rows.reverse()	rows: cols.reverse() cols: rows	rows: [2, 1, 1] cols: [1, 3]	rows: rows.reverse() cols: cols.reverse()
[[0, 1, 1], [0, 1, 1], [0, 0, 1]]	rows: cols.reverse() cols: rows	rows: cols cols: rows.reverse()	rows: rows.reverse() cols: cols.reverse()	rows: [1, 1, 2] cols: [3, 1]

• 하지만 이 방법에도 아래 "이전 코드와 문제점"에서 문제가 드러난다.
• 그래서 고안한 방법이 8방향 탐색과 꺾이는 지점 파악이다.
• 블록의 위치를 저장한 배열이 [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1]]일 때
  • [0, 0]을 기준으로
    • [0, 1]과 [1, 1]은 상하좌우에 속하므로 straight = 2
    • [1, 1]은 대각선이고 [0, 1]을 거쳐서 갈 수 있고 직진 우회전이므로 right = 1
    • 하지만 [1, 1]을 거쳐서 갈 수도 있으므로 직진 좌회전 left = 1
  • [2, 1, 1]로 된 배열을 가진다.
• 이를 키로 만들어서 위의 키와 합치면 하나밖에 없는 키가 만들어진다. 아마도...

• 이런식으로 직좌 직우 움직여서 확인하게 된다.

 

이전 코드와 문제점

• 8방향 탐색과 꺾이는 지점을 포착하고 좌우 어디로 꺾였는지 확인
• 테스트 케이스 10번만 틀림

function solution(game_board, table) {
    const n = table.length;
    // 키가 없으면 키는 eightDirections로 만든 newArr로 만든다.
    // 계산이 편하게 맨 앞은 count
    // 그리고 blank는 [1, 0] block은 [0, 1] 로 선언
    // 키가 있으면 각 키에 해당하는 값의 blank와 block의 index에 +1;
    const checkMap = new Map();
    
    // bfs
    const dr = [-1, 1, 0, 0, -1, -1, 1, 1];
    const dc = [0, 0, -1, 1, 1, -1, 1, -1];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < n;
    };
    const eightDirections = (arr, visited, lenA) => {
        const newArr = [];
        for (const [r, c] of arr) {
            let straight = 0;
            let left = 0;
            let right = 0;
            // 0 ~ 3는 같은 방향으로 취급하고 
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && visited[nr][nc]) {
                    straight++;
                }
            }
            // 4 ~ 7은 꺾이는 지점으로 한다.
            for (let d = 4; d < 8; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && visited[nr][nc]) {
                    // 오른쪽
                    // 같은 행에 정사각형이 있고
                    if (visited[r][nc]) {
                        // 오른쪽에 있으며
                        if (c < nc) {
                            // 행이 작은 경우 왼쪽
                            if (r > nr) {
                                left++;
                            } else {
                                right++;
                            }
                        } else {
                            // 왼쪽에 있으며
                            // 행이 작은 경우 오른쪽
                            if (r > nr) {
                                right++;
                            } else {
                                left++;
                            }
                        }
                    }
                    // 왼쪽
                    // 같은 열에 정사각형이 있고
                    if (visited[nr][c]) {
                        // 위에 있고
                        if (r > nr) {
                            // 열이 크면 오른쪽
                            if (c < nc) {
                                right++;
                            } else {
                                left++;
                            }
                        } else {
                            // 아래에 있고
                            // 열이 크면 왼쪽
                            if (c < nc) {
                                left++;
                            } else {
                                right++;
                            }
                        }
                    }
                }
            }
            newArr.push([straight, left, right]);
        }
        
        newArr.sort(([a, b, c], [d, e, f]) => a - d || b - e || c - f);
        return `${lenA}-${newArr}`;
    }
    const bfs = (sr, sc, isBlock) => {
        const deque = [[sr, sc]];
        const keys = [[sr, sc]];
        
        // 8방향 확인을 위한 visited
        const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));
        visited[sr][sc] = true;
        
        if (isBlock) {
            table[sr][sc] = 0; // 빈칸 채워서 더 못찾게 하기
        } else {
            game_board[sr][sc] = 1; // 빈칸 채워서 더 못찾게 하기
        }
        
        while (deque.length > 0) {
            const [r, c] = deque.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc)) {
                    if (isBlock && table[nr][nc] === 1) {
                        table[nr][nc] = 0;
                        deque.push([nr, nc]);
                        keys.push([nr, nc]);
                        visited[nr][nc] = true;
                    } else if (!isBlock && game_board[nr][nc] === 0) {
                        game_board[nr][nc] = 1;
                        deque.push([nr, nc]);
                        keys.push([nr, nc]);
                        visited[nr][nc] = true;
                    }
                }
            }
        }
        // 저장할 때 정렬해서 넣는다.
        // [[3, 2], [1, 3]] 이면
        // [[1, 3], [3, 2]]로 정렬한다.
        const cnt = keys.length;
        keys.sort(([a, b], [c, d]) => a - c || d - b);

        const newKeys = eightDirections(keys, visited, cnt);
        if (checkMap.has(newKeys)) {
            // [0, 0] 앞이 cnt blanks 뒤가 cnt blocks
            const checkValue = checkMap.get(newKeys);
            if (isBlock) {
                checkMap.set(newKeys, [checkValue[0], checkValue[1]+1]);
            } else {
                checkMap.set(newKeys, [checkValue[0]+1, checkValue[1]]);
            }
        } else {
            if (isBlock) {
                checkMap.set(newKeys, [0, 1]);
            } else {
                checkMap.set(newKeys, [1, 0]);
            }
        }
    }
    
    for (let sr = 0; sr < n; sr++) {
        for (let sc = 0; sc < n; sc++) {
            if (game_board[sr][sc] === 0) {
                bfs(sr, sc, false);
            }
            if (table[sr][sc] === 1) {
                bfs(sr, sc, true);
            }
        }
    }
    
    let answer = 0;
    // 계산
    let checkMapKeys = checkMap.keys();
    for (const cmk of checkMapKeys) {
        const count = cmk[0];
        const [cntBlanks, cntBlocks] = checkMap.get(cmk);
        answer += Math.min(cntBlanks, cntBlocks) * count;
    }
    return answer;
}

• 행에서 가로로 개수 파악, 열에서 세로로 개수 파악
  • 예를 들어 [[0, 1, 1], [0, 0, 1], [0, 1, 1]] 이라는 배열은
  • rows : 1, 2, 1
  • cols : 3, 1
• 테스트 케이스 10번은 맞으나 3, 7, 13, 22 틀림
• 예상 반례
  • game_board = [[0, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 0, 1]]
  • table = [[0, 0, 1, 0], [0, 1, 1, 0], [1, 1, 0, 0], [1, 0, 0, 0]]
  • output = 0

function solution(game_board, table) {
    let answer = 0;
    // 체크 맵
    let checkMap = new Map();
    const setMap = (key) => {
        if (checkMap.has(key)) {
            checkMap.set(key, checkMap.get(key)+1);
        } else {
            checkMap.set(key, 1);
        }
    }
    
    // 길이
    const n = game_board.length;
    
    // 방향 범위
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < n;
    };
    
    // bfs
    const bfs = (sr, sc, isBlock) => {
        const deque = [[sr, sc]];
        const rows = new Map();
        const cols = new Map();
        rows.set(sr, 1);
        cols.set(sc, 1);
        
        if (isBlock) {
            table[sr][sc] = 0; // 빈칸 채워서 더 못찾게 하기
        } else {
            game_board[sr][sc] = 1; // 빈칸 채워서 더 못찾게 하기
        }
        
        let count = 1;
        while (deque.length > 0) {
            const [r, c] = deque.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                let isTrue = false;
                if (isValid(nr, nc)) {
                    if (isBlock && table[nr][nc] === 1) {
                        table[nr][nc] = 0;
                        deque.push([nr, nc]);
                        isTrue = true;
                    } else if (!isBlock && game_board[nr][nc] === 0) {
                        game_board[nr][nc] = 1;
                        deque.push([nr, nc]);
                        isTrue = true;
                    }
                }
                if (isTrue) {
                    count++;
                    if (rows.has(nr)) {
                        rows.set(nr, rows.get(nr)+1);
                    } else {
                        rows.set(nr, 1);
                    }
                    if (cols.has(nc)) {
                        cols.set(nc, cols.get(nc)+1);
                    } else {
                        cols.set(nc, 1);
                    }
                }
            }
        }
        // 행 키
        const rowsEntries = [...(rows.entries())].map((e) => e);
        rowsEntries.sort(([a, b], [c, e]) => a - c);
        const rowsKeys = rowsEntries.map((e) => e[1]);
        // 열 키
        const colsEntries = [...(cols.entries())].map((e) => e);
        colsEntries.sort(([a, b], [c, e]) => a - c);
        const colsKeys = colsEntries.map((e) => e[1]);
        
        const cr = [...colsKeys].reverse();
        const rr = [...rowsKeys].reverse();
        
        const firstKey = `${count}-${rowsKeys}-${colsKeys}`;
        const secondKey = `${count}-${cr}-${rowsKeys}`;
        
        const thirdKey = `${count}-${rr}-${cr}`; 
        const fourthKey = `${count}-${colsKeys}-${rr}`;

        // set에 넣어야 함
        const set = new Set([firstKey, secondKey, thirdKey, fourthKey]);
        // 블럭이면 확인하고 있으면 둘 다 -1 
        if (isBlock) {
            // key 둘 중에 하나는 있을 것이다.
            if (checkMap.has(firstKey)) {
                if (checkMap.get(firstKey) > 0) {
                    // 둘 중 하나만 탐색해도 있겠지만 둘 다 지워야 한다.
                    for (const sv of set) {
                        checkMap.set(sv, checkMap.get(sv)-1);
                    }
                    // answer에 count만큼 저장
                    answer += count;
                }
            } 
        } else {
            // 빈칸을 체크맵에 저장
            for (const sv of set) {
                setMap(sv);
            };
        }
    }
    
    // 빈칸 먼저 저장하고
    for (let sr = 0; sr < n; sr++) {
        for (let sc = 0; sc < n; sc++) {
            if (game_board[sr][sc] === 0) {
                bfs(sr, sc, false);
            }
        }
    }
    
    // 블록으로 빈칸에 넣을 수 있는지 확인
    for (let sr = 0; sr < n; sr++) {
        for (let sc = 0; sc < n; sc++) {
            if (table[sr][sc] === 1) {
                bfs(sr, sc, true);
            }
        }
    }
    return answer;
}

느낀점

• 무슨 홍대병에 걸린 것 마냥 내 방식대로 끝까지 고집해서 풀었다.
• 남들이 푸는 도형 90 180 270도 돌리는 방향으로 풀었으면 3일이라는 시간보다 빠르게 풀었을 것 같다.
• "simple is best" 단순하게 생각해서 도형 돌리는 방법으로 나중에 다시 풀어보면 좋을 것 같다.