[BOJ] 16988 - Baaaaaaaaaduk2 (Easy) (Python, JavaScript)

 

 

아이디어

 

BFS와 브루트포스로 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 개수를 구한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    cnt_dict = dict()
    pos = set()
    res = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 2:
                queue = [(i, j)]
                board[i][j] = 1
                cnt = 0
                kill = 1
                temp = []
                while queue:
                    r, c = queue.pop()
                    for dr, dc in delta:
                        nr, nc = r+dr, c+dc
                        if N > nr >= 0 and M > nc >= 0:
                            if board[nr][nc] != 1:
                                if board[nr][nc] == 0:
                                    temp.append((nr, nc))
                                    cnt += 1
                                elif board[nr][nc] == 2:
                                    queue.append((nr, nc))
                                    kill += 1
                                board[nr][nc] = 1
                for r, c in temp:
                    board[r][c] = 0
                if cnt == 0:
                    res += kill
                elif cnt <= 2:
                    for p in temp:
                        pos.add(p)
                    if cnt > 1:
                        temp = tuple(temp)
                    else:
                        temp = tuple(*temp)
                    cnt_dict[temp] = cnt_dict.get(temp, 0)+kill
    pos.add((-1, -1))
    pos = tuple(pos)
    for p1 in pos:
        for p2 in pos:
            if p1 == p2:
                continue
            kill = cnt_dict.get(p1, 0)+cnt_dict.get(p2, 0)+cnt_dict.get((p1, p2), 0)+cnt_dict.get((p2, p1), 0)
            if kill > res:
                res = kill
    print(res)

solution()

 

 

 

풀이 #2 (JavaScript)

 

맵에 저장하는 키 값을 문자열로 변환하여 값을 저장한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    const [N, M] = input[0].split(' ').map(Number);
    let board = [];
    for (let i=1; i<=N; i++) {
        board.push(input[i].split(' ').map(Number));
    }
    const delta = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    let cntMap = new Map();
    let pos = new Set();
    let res = 0;
    for (let i=0; i<N; i++) {
        for (let j=0; j<M; j++) {
            if (board[i][j] === 2) {
                let queue = [[i, j]];
                board[i][j] = 1;
                let cnt = 0;
                let kill = 1;
                let temp = [];
                while (queue.length) {
                    const [r, c] = queue.pop();
                    for (const [dr, dc] of delta) {
                        const [nr, nc] = [r+dr, c+dc];
                        if (nr < N && nr >= 0 && nc < M && nc >= 0) {
                            if (board[nr][nc] !== 1) {
                                if (board[nr][nc] === 0) {
                                    temp.push([nr, nc]);
                                    cnt += 1;
                                }
                                else if (board[nr][nc] === 2) {
                                    queue.push([nr, nc]);
                                    kill += 1;
                                }
                                board[nr][nc] = 1;
                            }
                        }
                    }
                }
                for (const [r, c] of temp) board[r][c] = 0;
                if (cnt === 0) {
                    res += kill;
                }
                else if (cnt <= 2) {
                    let key = [];
                    for (const p of temp) {
                        pos.add(p.join(','));
                        key.push(p.join(','));
                    };
                    key = key.join(',');
                    cntMap.set(key, (cntMap.get(key) ? cntMap.get(key) : 0)+kill);
                }
            }
        }
    }
    pos.add('-1,-1');
    for (const p1 of pos) {
        for (const p2 of pos) {
            if (p1 === p2) continue;
            const cnt1 = cntMap.get(p1) ? cntMap.get(p1) : 0;
            const cnt2 = cntMap.get(p2) ? cntMap.get(p2) : 0;
            const cnt3 = cntMap.get([p1, p2].join(',')) ? cntMap.get([p1, p2].join(',')) : 0;
            const cnt4 = cntMap.get([p2, p1].join(',')) ? cntMap.get([p2, p1].join(',')) : 0;
            const kill = cnt1+cnt2+cnt3+cnt4;
            if (kill > res) res = kill;
        }
    }
    console.log(res);
}

solution();