[알고리즘, 코드트리] 왕실의 기사 대결 - java

문제

문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

요약하자면 아래와 같다. 총 두 가지 동작을 수행해야 한다.

(1) 기사 이동 : 왕에게 명령을 받은 기사는 상하좌우 중 하나로 한 칸 이동할 수 있습니다. 이때 만약 이동하려는 위치에 다른 기사가 있다면 그 기사도 함께 연쇄적으로 한 칸 밀려나게 됩니다. 그 옆에 또 기사가 있다면 연쇄적으로 한 칸씩 밀리게 됩니다. 하지만 만약 기사가 이동하려는 방향의 끝에 벽이 있다면 모든 기사는 이동할 수 없게 됩니다. 또, 체스판에서 사라진 기사에게 명령을 내리면 아무런 반응이 없게 됩니다.

(2) 대결 대미지 : 명령을 받은 기사가 다른 기사를 밀치게 되면, 밀려난 기사들은 피해를 입게 됩니다. 이때 각 기사들은 해당 기사가 이동한 곳에서 w×h 직사각형 내에 놓여 있는 함정의 수만큼만 피해를 입게 됩니다. 각 기사마다 피해를 받은 만큼 체력이 깎이게 되며, 현재 체력 이상의 대미지를 받을 경우 기사는 체스판에서 사라지게 됩니다.

입력

첫 번째 줄에 L, N, Q가 공백을 사이에 두고 주어집니다.

다음 L 개의 줄에 걸쳐서 L×L 크기의 체스판에 대한 정보가 주어집니다.

• 0이라면 빈칸을 의미합니다.
• 1이라면 함정을 의미합니다.
• 2라면 벽을 의미합니다.

다음 N 개의 줄에 걸쳐서 초기 기사들의 정보가 주어집니다. 이 정보는 (r,c,h,w,k) 순으로 주어지며, 이는 기사의 처음 위치는 (r,c)를 좌측 상단 꼭지점으로 하며 세로 길이가 h, 가로 길이가 w인 직사각형 형태를 띄고 있으며 초기 체력이 k라는 것을 의미합니다. 입력은 1번 기사부터 N번 기사까지 순서대로 정보가 주어집니다.

단, 처음 주어지는 기사들의 위치는 기사들끼리 서로 겹쳐져 있지 않습니다. 또한 기사와 벽은 겹쳐서 주어지지 않습니다.

다음 Q 개의 줄에 걸쳐 왕의 명령에 대한 정보가 주어집니다. 이 정보는 (i,d) 형태로 주어지며 이는 i번 기사에게 방향 d로 한 칸 이동하라는 명령임을 뜻합니다. i는 1 이상 N 이하의 값을 갖으며, 이미 사라진 기사 번호가 주어질 수도 있음에 유의합니다. d는 0, 1, 2, 3 중에 하나이며 각각 위쪽, 오른쪽, 아래쪽, 왼쪽 방향을 의미합니다.

• L: 체스판의 크기 (3≤L≤40)
• N: 기사의 수 (1≤N≤30)
• Q: 명령의 수 (1≤Q≤100)
• k: 기사의 체력 (1≤k≤100)

출력

Q 개의 명령이 진행된 이후, 생존한 기사들이 총 받은 대미지의 합을 출력합니다.

문제 풀이

바로 직전에 풀었던 문제가 "코드트리 메신저"와 "코드트리 오마카세" 였어서 그런가... 왕실의 기사 대결 문제는 아주 선녀처럼 보였다. 이 글을 읽는 사람들도 어렵지 않게 따라 생각해 낼 수 있는 풀이라고 느낀다. 두려움을 없애고 차분히 도전해 보자.

자료구조 정의 및 입출력

static int[][] map;

static class Knight {
    int r;
    int c;
    int h;
    int w;
    int k;

    boolean out = false;
    int damage = 0;

    Knight(int r, int c, int h, int w, int k) {
        this.r = r;
        this.c = c;
        this.h = h;
        this.w = w;
        this.k = k;
    }
}

static Map<Integer, Knight> knightMap = new HashMap<>();
static ArrayList<Integer> knightArr = new ArrayList<>();

static int[] dy = {-1,0,1,0};
static int[] dx = {0,1,0,-1};

지금까지 다양한 삼성 SW 역량 테스트를 풀어보니 기본적인 자료구조 선언에 대해서 시행착오 없이 진행할 수 있게 되었다.

 

이번 문제에서는 기사의 정보를 저장할 Knight 클래스를 정의하였다. 이 Knight 클래스를 id 기준으로 저장할 knightMap과 모든 기사의 id를 저장하고 있는 knightArr를 이용하여 저장할 것이다.

 

이때, Knight 클래스에서는 현재까지 받은 피해의 총량인 int damage 멤버 변수와 Knight가 아직 체스판 위에 존재하는지를 나타낼 boolean out 멤버 변수를 넣어준다.

L = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());

map = new int[L + 1][L + 1];
for(int y = 1; y <= L; y++) {
    st = new StringTokenizer(br.readLine());
    for(int x = 1; x <= L; x++) {
        map[y][x] = Integer.parseInt(st.nextToken());
    }
}

for(int i = 1; i <= N; i++) {
    st = new StringTokenizer(br.readLine());

    int r = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    int h = Integer.parseInt(st.nextToken());
    int w = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    knightMap.put(i, new Knight(r, c, h, w, k));
    knightArr.add(i);
}

while(Q-- > 0) {
    st = new StringTokenizer(br.readLine());

    int i = Integer.parseInt(st.nextToken());
    int d = Integer.parseInt(st.nextToken());
	
    // 주어진 정보를 기반으로 기사를 밀어본다.
    push(i , d);
}

main 함수가 다른 기출문제에 비해서 상당히 간단하게 구조화되었다. 모든 정보를 입력받고 단순히 기사의 id와 방향을 주고 밀어보라고 주문할 것이다.

밀어봐 _ push()

static void push(int id, int d) {
    int[][] temp = init();

    Knight knight = knightMap.get(id);
    if(knight.out) {
        return;
    }

    // 움직일 방향에 대해서 다른 기사에게 영향을 끼치는 좌표의 목록
    ArrayList<int[]> posArr = getPosArr(id, d);
    
    Queue<int[]> pos = new ArrayDeque<>();
    pos.addAll(posArr);

    // pos에서 하나씩 꺼내서 d 방향으로 한칸씩 이동할 거임.
    // 이 때 만나는 id를 Set에 저장
    // 벽을 만나면 움직일 수 없음
    Set<Integer> knightSet = new HashSet<>();
    boolean enableToMove = true;
    while(!pos.isEmpty()) {
        int[] now = pos.poll();
        int nextY = now[0] + dy[d];
        int nextX = now[1] + dx[d];

        // 벽을 만나면
        if(nextY <= 0 || nextY > L || nextX <= 0 || nextX > L) {
            enableToMove = false;
            break;
        }
        if(map[nextY][nextX] == 2) {
            enableToMove = false;
            break;
        }

        if(temp[nextY][nextX] > 0 && !knightSet.contains(temp[nextY][nextX])) {
            knightSet.add(temp[nextY][nextX]);
            posArr = getPosArr(temp[nextY][nextX], d);
            pos.addAll(posArr);
        }
    }

    // 움직일 수 없다면 바로 종료
    if(!enableToMove) {
        return;
    }

    moveKnights(knight, knightSet, d);
}

push 함수는 bfs의 응용이라고 할 수 있다.

(1) 가장 처음으로 할 일은 벽과 함정의 정보를 저장하고 있는 전역 2차원 배열인 map과는 별도로 기사들의 위치를 표현하고 있는 2차원 배열 temp를 초기화해주어야 한다.

 

(2) 그 후, 기사가 움직일 방향에 대해서 다른 기사에게 영향을 끼칠 수 있는 좌표의 목록을 가져와 Queue에 집어넣는다.

 

(3) 이제 Queue에서 하나씩 좌표를 꺼내보며 주어진 방향(d)으로 한 칸 나아갔을 때 다른 기사가 있는지 확인하자. 만약 다른 기사가 있다면 그 기사도 주어진 방향(d)으로 밀려나야 하므로 그 기사가 또 다른 기사에게 영향을 끼칠 수 있는 좌표의 목록을 Queue에 집어넣는다.

 

(4) 이 와중에 벽을 만나면 모든 기사는 움직일 수 없으므로 enableToMove라는 Flag값을 false로 만들어준다.

 

(5) 마지막으로 Flag가 true였다면 영향을 받았던 기사들을 d방향으로 한 칸씩 밀어준다.

 

push 함수의 구조화를 마쳤다. 어려운 설명이었지만 이해를 돕기 위한 그림과 함께 다시 한번 자세히 설명해 주겠다.

기사들의 위치를 표현 _ init()

static int[][] init() {
    int[][] temp = new int[L + 1][L + 1];

    for(int id : knightArr) {
        Knight knight = knightMap.get(id);

        if(knight.out) {
            continue;
        }

        for(int y = 0; y < knight.h; y++) {
            for(int x = 0; x < knight.w; x++) {
                temp[knight.r + y][knight.c + x] = id;
            }
        }
    }

    return temp;
}

어렵지 않다. 체스판에 남아있는 기사들을 기사들의 size만큼 temp라는 2차원 배열에 기록해 주면 된다. 기사들의 위치는 전역적으로 관리하지 않고 매 라운드마다 갱신되는 knight.r과 knight.c를 반영하여 새롭게 그려줄 것이다.

다른 기사에게 영향을 끼칠 수 있는 좌표? _ getPosArr()

static ArrayList<int[]> getPosArr(int id, int d) {
    Knight knight = knightMap.get(id);

    // 움직일 방향의 벽면 좌표 가져오기
    ArrayList<int[]> pos = new ArrayList<>();
    if(d == 0) {
        for(int i = 0; i < knight.w; i++) {
            pos.add(new int[] {knight.r, knight.c + i});
        }
    } else if(d == 1) {
        for(int i = 0; i < knight.h; i++) {
            pos.add(new int[] {knight.r + i, knight.c + (knight.w - 1)});
        }
    } else if(d == 2) {
        for(int i = 0; i < knight.w; i++) {
            pos.add(new int[] {knight.r + (knight.h - 1), knight.c + i});
        }
    } else if(d == 3) {
        for(int i = 0; i < knight.h; i++) {
            pos.add(new int[] {knight.r + i, knight.c});
        }
    }

    return pos;
}

아까부터 계속 얘기하던 다른 기사에게 영향을 끼칠 수 있는 좌표의 목록은 위와 같이 구할 수 있다. 기사가 d 방향으로 한 칸 전진하기 위해선 해당방향에 존재하는 마지막 좌표들의 조합만 신경 쓰면 된다. 아래 그림을 보자.

이때, 1번 기사가 2번 기사를 밀게 되므로 push() 함수 안에서 2번 기사도 다른 체스칸에 영향을 줄 수 있다. 따라서, 2번 기사에 대해서도 다른 기사에게 영향을 끼칠 수 있는 좌표의 목록을 뽑아 응용 bfs Queue에 넣어 준다.

3번 기사도 영향받는 블록이 d 방향으로 한 칸 밀리게 되는데 이때 벽(4, 3)을 만나게 된다. 따라서 모든 기사들은 움직일 수 없다.

 

두 번째 경우까지 살펴보자. 이번엔 2번 기사를 1방향으로 한 칸 이동시킬 것이다. 2번 기사가 다른 기사에게 영향을 끼칠 수 있는 블록은 아래 그림처럼 (2, 1)과 (3, 1)이다.

헷갈리지 말자.. (y, x)로 작성해 두었다....

(2, 1)이 1번 기사와 맞닿게 되므로 1번 기사도 d 방향으로 이동하게 된다. 1번 기사가 영향을 끼칠 수 있는 블록 또한 아래 그림처럼 (1, 2)와 (2, 2)이다.

(3, 1)이 3번 기사와 맞닿게 되므로 3번 기사도 d 방향으로 이동한다. 1번 기사가 영향을 끼칠 수 있는 블록 또한 아래 그림처럼 (3, 3)이다.

기사들을 움직이자 _ moveKnights()

static void moveKnights(Knight knight, Set<Integer> knightSet, int d) {
    knight.r += dy[d];
    knight.c += dx[d];

    for(int movedKnightid : knightSet) {
        Knight movedKnight = knightMap.get(movedKnightid);

        movedKnight.r += dy[d];
        movedKnight.c += dx[d];

        int damaged = 0;
        for(int y = 0; y < movedKnight.h; y++) {
            for(int x = 0; x < movedKnight.w; x++) {
                // 밀려서 밟고 있는 함정의 수
                if(map[movedKnight.r + y][movedKnight.c + x] == 1) {
                    damaged++;
                }
            }
        }

        movedKnight.damage += damaged;
        movedKnight.k -= damaged;
        if(movedKnight.k <= 0) {
            movedKnight.out = true;
        }
    }
}

push 함수의 bfs 응용에서 영향받게 되는 기사들은 전부 Set에 저장해 두었다. moveKnight() 함수에서는 움직일 방향과 Set을 파라미터로 받고 해당 방향으로 kight들의 r과 c를 움직여 준다. 이때, 밀려난 기사가 밟고 있는 함정의 수가 기사가 해당 라운드에 받게 될 피해의 크기이다.

 

피해의 크기를 계산했을 때, 남아있는 체력이 0 이하가 된다면 그 기사는 체스판에서 퇴장한다.

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int L, N, Q;
    static int[][] map;

    static class Knight {
        int r;
        int c;
        int h;
        int w;
        int k;

        boolean out = false;
        int damage = 0;

        Knight(int r, int c, int h, int w, int k) {
            this.r = r;
            this.c = c;
            this.h = h;
            this.w = w;
            this.k = k;
        }
    }

    static Map<Integer, Knight> knightMap = new HashMap<>();
    static ArrayList<Integer> knightArr = new ArrayList<>();

    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,1,0,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        map = new int[L + 1][L + 1];
        for(int y = 1; y <= L; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x = 1; x <= L; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            knightMap.put(i, new Knight(r, c, h, w, k));
            knightArr.add(i);
        }

        while(Q-- > 0) {
            st = new StringTokenizer(br.readLine());

            int i = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            push(i , d);
        }

        int result = 0;
        for(int id : knightArr) {
            Knight knight = knightMap.get(id);

            if(!knight.out) {
                result += knight.damage;
            }
        }
        System.out.println(result);
    }

    static void push(int id, int d) {
        int[][] temp = init();

        Knight knight = knightMap.get(id);
        if(knight.out) {
            return;
        }

        // 움직일 방향에 대해서 다른 기사에게 영향을 끼치는 좌표의 목록
        ArrayList<int[]> posArr = getPosArr(id, d);
        
        Queue<int[]> pos = new ArrayDeque<>();
        pos.addAll(posArr);

        // pos에서 하나씩 꺼내서 d 방향으로 한칸씩 이동할 거임.
        // 이 때 만나는 id를 Set에 저장
        // 벽을 만나면 움직일 수 없음
        Set<Integer> knightSet = new HashSet<>();
        boolean enableToMove = true;
        while(!pos.isEmpty()) {
            int[] now = pos.poll();
            int nextY = now[0] + dy[d];
            int nextX = now[1] + dx[d];

            // 벽을 만나면
            if(nextY <= 0 || nextY > L || nextX <= 0 || nextX > L) {
                enableToMove = false;
                break;
            }
            if(map[nextY][nextX] == 2) {
                enableToMove = false;
                break;
            }

            if(temp[nextY][nextX] > 0 && !knightSet.contains(temp[nextY][nextX])) {
                knightSet.add(temp[nextY][nextX]);
                posArr = getPosArr(temp[nextY][nextX], d);
                pos.addAll(posArr);
            }
        }

        // 움직일 수 없다면 바로 종료
        if(!enableToMove) {
            return;
        }

        moveKnights(knight, knightSet, d);
    }

    static ArrayList<int[]> getPosArr(int id, int d) {
        Knight knight = knightMap.get(id);

        // 움직일 방향의 벽면 좌표 가져오기
        ArrayList<int[]> pos = new ArrayList<>();
        if(d == 0) {
            for(int i = 0; i < knight.w; i++) {
                pos.add(new int[] {knight.r, knight.c + i});
            }
        } else if(d == 1) {
            for(int i = 0; i < knight.h; i++) {
                pos.add(new int[] {knight.r + i, knight.c + (knight.w - 1)});
            }
        } else if(d == 2) {
            for(int i = 0; i < knight.w; i++) {
                pos.add(new int[] {knight.r + (knight.h - 1), knight.c + i});
            }
        } else if(d == 3) {
            for(int i = 0; i < knight.h; i++) {
                pos.add(new int[] {knight.r + i, knight.c});
            }
        }

        return pos;
    }

    static int[][] init() {
        int[][] temp = new int[L + 1][L + 1];

        for(int id : knightArr) {
            Knight knight = knightMap.get(id);

            if(knight.out) {
                continue;
            }

            for(int y = 0; y < knight.h; y++) {
                for(int x = 0; x < knight.w; x++) {
                    temp[knight.r + y][knight.c + x] = id;
                }
            }
        }

        return temp;
    }

    static void moveKnights(Knight knight, Set<Integer> knightSet, int d) {
        knight.r += dy[d];
        knight.c += dx[d];

        for(int movedKnightid : knightSet) {
            Knight movedKnight = knightMap.get(movedKnightid);

            movedKnight.r += dy[d];
            movedKnight.c += dx[d];

            int damaged = 0;
            for(int y = 0; y < movedKnight.h; y++) {
                for(int x = 0; x < movedKnight.w; x++) {
                    // 밀려서 밟고 있는 함정의 수
                    if(map[movedKnight.r + y][movedKnight.c + x] == 1) {
                        damaged++;
                    }
                }
            }

            movedKnight.damage += damaged;
            movedKnight.k -= damaged;
            if(movedKnight.k <= 0) {
                movedKnight.out = true;
            }
        }
    }
}

문제 풀이 소요 시간 : 1시간 반