[ 백준 ] 20165 인내의 도미노 장인 호석

📌 Problem

수비수를 구현하는 것을 크게 어렵지 않다. 실제 구현에 중요한 것을 공격수이다. 공격수의 구현 방법은 다음과 같다.

5개의 도미노가 다음과 같이 있다고 가정해보자.

각각의 숫자는 도미노의 높이이다. 여기서 높이가 3인 도미노를 동쪽으로 넘어뜨린다. 높이가 3이며 현재 인덱스가 0이기 때문에 0 + 3이 너머진 도미노의 경계값이다. 즉, index 2까지 영향을 미친다. (경계값은 넘어진 도미노가 영향을 미치는 도미노 직후의 인덱스이다.) 이후 index 1의 도미노도 같이 넘어진다. 이때 index 1의 도미노 경계값은 1 + 1 = 2 이다. 기존 경계값 3이 더 크기 때문에 넘어간다. index 2의 도미노도 같이 넘어진다. 이때 도미노 경계값은 2 + 2 = 4이다. 기존 경계값보다 커졌기 때문에 경계값을 4로 업데이트한다. index 3과 4도 동일한 방법으로 이루어진다.

📌 Solution

결과적으로 도미노들이 넘어지면서 어디까지 영향을 미치는가를 계속 업데이트 해주면 된다. 코드로 간략하게 표현하면 다음과 같다.

Domino domino = 넘어뜨리는 도미노
int limit = domino.index + domino.height;
for (int index = domino.index; index < limit; index++) {
	domino = dominoes.get(idnex);
	if (domino.isStanding()) {
    	domino.knockDown();
        attackerPoint++;
        limit = Math.max(limit, index + domino.height);
    }
}

다만, 문제는 4방향으로 넘어뜨릴 수 있고 2차원으로 도미노들이 있다는 점이다. 이를 각각의 방향으로 나누어서 생각하면 다음과 같다.

public void attack(int row, int col, char dir) {
    Domino domino = dominoes[row][col];
    if (domino.isStanding()) {
        switch (dir) {
            case 'N': {
                int limitRow = row - domino.getHeight();
                for (int r = row; r > limitRow; r--) {
                    try {
                        domino = dominoes[r][col];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitRow = Math.min(limitRow, r - domino.getHeight());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
            case 'E': {
                int limitCol = col + domino.getHeight();
                for (int c = col; c < limitCol; c++) {
                    try {
                        domino = dominoes[row][c];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitCol = Math.max(limitCol, c + domino.getHeight());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
            case 'S': {
                int limitRow = row + domino.getHeight();
                for (int r = row; r < limitRow; r++) {
                    try {
                        domino = dominoes[r][col];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitRow = Math.max(limitRow, r + domino.getHeight());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
            case 'W': {
                int limitCol = col - domino.getHeight();
                for (int c = col; c > limitCol; c--) {
                    try {
                        domino = dominoes[row][c];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitCol = Math.min(limitCol, c - domino.getHeight());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
        }
    }
}

이렇게 각 방향별로 구현이 가능하지만 이는 좋은 코드가 아니다. 그래서 몇개의 단계를 통해 코드를 줄인다.

Step 1. Direction enum class
방향은 동서남북으로 고정되어 있으며 row와 col의 업데이트 수치도 동일하다. 이를 enum class으로 만들어서 관리한다.

public enum Direction {
    NORTH('N', -1, 0),
    EAST('E', 0, 1),
    SOUTH('S', 1, 0),
    WEST('W', 0, -1);

    private final char dir;
    private final int row, col;

    Direction(char dir, int row, int col) {
        this.dir = dir;
        this.row = row;
        this.col = col;
    }

    public static Direction create(char dir) {
        for (Direction direction : values())
            if (direction.dir == dir) return direction;
        throw new RuntimeException("Wrong direction type");
    }
}

이를 적용하여 공경 함수를 다음과 같이 변경한다.

public void attack(int row, int col, char dir) {
    Domino domino = dominoes[row][col];
    if (domino.isStanding()) {
        Direction direction = Direction.create(dir);
        switch (dir) {
            case 'N': {
                int limitRow = row + domino.getHeight() * direction.row();
                for (int r = row; r > limitRow; r += direction.row()) {
                    try {
                        domino = dominoes[r][col];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitRow = Math.min(limitRow, r + domino.getHeight() * direction.row());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
            case 'E': {
                int limitCol = col + domino.getHeight() * direction.col();
                for (int c = col; c < limitCol; c += direction.col()) {
                    try {
                        domino = dominoes[row][c];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitCol = Math.max(limitCol, c + domino.getHeight() * direction.col());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
            case 'S': {
                int limitRow = row + domino.getHeight() * direction.row();
                for (int r = row; r < limitRow; r += direction.row()) {
                    try {
                        domino = dominoes[r][col];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitRow = Math.max(limitRow, r + domino.getHeight() * direction.row());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
            case 'W': {
                int limitCol = col + domino.getHeight() * direction.col();
                for (int c = col; c > limitCol; c += direction.col()) {
                    try {
                        domino = dominoes[row][c];
                        if (domino.isStanding()) {
                            domino.knock();
                            attackScore++;
                            limitCol = Math.min(limitCol, c + domino.getHeight() * direction.col());
                        }
                    } catch (ArrayIndexOutOfBoundsException e) {
                        break;
                    }
                }
                break;
            }
        }
    }
}

Step 2. 비슷한 경우 묶기
코드를 보면 row와 column이 양수 방향으로 진행할 때와 음수 방향으로 진행할 때 비슷하다는 것을 알 수 있다. 그렇기 때문에 동남 방향과 북서 방향으로 코드를 묶는다.

public void attack(int row, int col, char dir) {
    Domino domino = dominoes[row][col];
    if (domino.isStanding()) {
        Direction direction = Direction.create(dir);
        int limitRow = row + domino.getHeight() * direction.row();
        int limitCol = col + domino.getHeight() * direction.col();
        if (dir == 'N' || dir == 'W') {
            for (int r = row, c = col; r > limitRow || c > limitCol; r += direction.row(), c += direction.col()) {
                try {
                    domino = dominoes[r][c];
                    if (domino.isStanding()) {
                        domino.knock();
                        attackScore++;
                        limitRow = Math.min(limitRow, r + domino.getHeight() * direction.row());
                        limitCol = Math.min(limitCol, c + domino.getHeight() * direction.col());
                    }
                } catch (ArrayIndexOutOfBoundsException e) {
                    break;
                }
            }
        } else if (dir == 'E' || dir == 'S') {
            for (int r = row, c = col; r < limitRow || c < limitCol; r += direction.row(), c += direction.col()) {
                try {
                    domino = dominoes[r][c];
                    if (domino.isStanding()) {
                        domino.knock();
                        attackScore++;
                        limitRow = Math.max(limitRow, r + domino.getHeight() * direction.row());
                        limitCol = Math.max(limitCol, c + domino.getHeight() * direction.col());
                    }
                } catch (ArrayIndexOutOfBoundsException e) {
                    break;
                }
            }
        }
    }
}

Step 3. 전체 묶기
최종적으로 동서남북의 경우를 다음과 같이 하나로 묶는다.

public void attack(int row, int col, char dir) {
    Domino domino = dominoes[row][col];
    if (domino.isStanding()) {
        Direction direction = Direction.create(dir);
        int limitRow = row + domino.getHeight() * direction.row();
        int limitCol = col + domino.getHeight() * direction.col();
        for (
                int r = row, c = col;
                r * direction.row() < limitRow * direction.row() || c * direction.col() < limitCol * direction.col();
                r += direction.row(), c += direction.col()
        ) {
            try {
                domino = dominoes[r][c];
                if (domino.isStanding()) {
                    domino.knock();
                    attackScore++;
                    if (dir == 'N' || dir == 'W') {
                        limitRow = Math.min(limitRow, r + domino.getHeight() * direction.row());
                        limitCol = Math.min(limitCol, c + domino.getHeight() * direction.col());
                    } else if (dir == 'E' || dir == 'S') {
                        limitRow = Math.max(limitRow, r + domino.getHeight() * direction.row());
                        limitCol = Math.max(limitCol, c + domino.getHeight() * direction.col());
                    }
                }
            } catch (ArrayIndexOutOfBoundsException e) {
                break;
            }
        }
    }
}

📌 Code

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
int R = Integer.parseInt(tokenizer.nextToken());

Board board = new Board(N, M);

for (int row = 0; row < N; row++) {
    tokenizer = new StringTokenizer(reader.readLine());
    for (int col = 0; col < M; col++) {
        board.addDomino(row, col, Integer.parseInt(tokenizer.nextToken()));
    }
}

while (R-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    int row = Integer.parseInt(tokenizer.nextToken()) - 1;
    int col = Integer.parseInt(tokenizer.nextToken()) - 1;
    char dir = tokenizer.nextToken().charAt(0);
    board.attack(row, col, dir);
    tokenizer = new StringTokenizer(reader.readLine());
    row = Integer.parseInt(tokenizer.nextToken()) - 1;
    col = Integer.parseInt(tokenizer.nextToken()) - 1;
    board.defense(row, col);
}

result.append(board.getAttackScore()).append('\n');
result.append(board);

class Board {

    private final Domino[][] dominoes;
    private int attackScore = 0;

    public Board(int row, int col) {
        dominoes = new Domino[row][col];
    }

    public void addDomino(int row, int col, int height) {
        dominoes[row][col] = new Domino(height);
    }

    public void attack(int row, int col, char dir) {
        Domino domino = dominoes[row][col];
        if (domino.isStanding()) {
            Direction direction = Direction.create(dir);
            int limitR = row + direction.row() * domino.getHeight();
            int limitC = col + direction.col() * domino.getHeight();
            for (int r = row, c = col;
                 r * direction.row() < limitR * direction.row() || c * direction.col() < limitC * direction.col();
                 r += direction.row(), c += direction.col()) {
                try {
                    domino = dominoes[r][c];
                    if (domino.isStanding()) {
                        attackScore++;
                        domino.knock();
                        limitR = direction.row() >= 0 ? Math.max(limitR, r + direction.row() * domino.getHeight()) :
                                Math.min(limitR, r + direction.row() * domino.getHeight());
                        limitC = direction.col() >= 0 ? Math.max(limitC, c + direction.col() * domino.getHeight()) :
                                Math.min(limitC, direction.col() * domino.getHeight());
                    }
                } catch (ArrayIndexOutOfBoundsException e) {
                    break;
                }
            }
        }
    }

    public void defense(int row, int col) {
        dominoes[row][col].stand();
    }

    public int getAttackScore() {
        return attackScore;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (Domino[] dominoes : dominoes) {
            for (Domino domino : dominoes)
                builder.append(domino.isStanding() ? 'S' : 'F').append(' ');
            builder.append('\n');
        }
        return builder.toString();
    }
}

class Domino {

    private final int height;
    private boolean standing = true;

    public Domino(int height) {
        this.height = height;
    }

    public void knock() {
        standing = false;
    }

    public void stand() {
        standing = true;
    }

    public int getHeight() {
        return height;
    }

    public boolean isStanding() {
        return standing;
    }
}

enum Direction {
    NORTH('N', -1, 0),
    EAST('E', 0, 1),
    SOUTH('S', 1, 0),
    WEST('W', 0, -1);

    private final char dir;
    private final int row, col;

    Direction(char dir, int row, int col) {
        this.dir = dir;
        this.row = row;
        this.col = col;
    }

    public static Direction create(char dir) {
        for (Direction direction : values())
            if (direction.dir == dir) return direction;
        throw new RuntimeException("Wrong direction type");
    }

    public int row() {
        return row;
    }

    public int col() {
        return col;
    }
}