[코드트리] 왕실의 기사 대결 feat. JAVA
삼성 코딩테스트 대비로 한 문제씩 풀어보려고 한다.
회사 다니면서 준비하느라 시간을 많이 할애하지 못해서 그냥 생각해보는 것에 의의를 두고 하려고 한다.
문제를 보고 한시간 안에 못하면 그냥 답을 보고 답지를 만들어보는 방식으로 준비하려고 한다.
오늘은 삼성 SDI 현직자 친구가 기출 중에 추천해준 문제인 '왕실의 기사 대결' 이다.
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
왕실의 기사 대결
왕실의 기사들은 L×L 크기의 체스판 위에서 대결을 준비하고 있습니다. 체스판의 왼쪽 상단은 (1,1)로 시작하며, 각 칸은 빈칸, 함정, 또는 벽으로 구성되어 있습니다. 체스판 밖도 벽으로 간주합니다.
왕실의 기사들은 자신의 마력으로 상대방을 밀쳐낼 수 있습니다. 각 기사의 초기위치는 (r,c)로 주어지며, 그들은 방패를 들고 있기 때문에 (r,c)를 좌측 상단으로 하며 h(높이)×w(너비) 크기의 직사각형 형태를 띄고 있습니다. 각 기사의 체력은 k로 주어집니다.
(1) 기사 이동
왕에게 명령을 받은 기사는 상하좌우 중 하나로 한 칸 이동할 수 있습니다. 이때 만약 이동하려는 위치에 다른 기사가 있다면 그 기사도 함께 연쇄적으로 한 칸 밀려나게 됩니다. 그 옆에 또 기사가 있다면 연쇄적으로 한 칸씩 밀리게 됩니다. 하지만 만약 기사가 이동하려는 방향의 끝에 벽이 있다면 모든 기사는 이동할 수 없게 됩니다. 또, 체스판에서 사라진 기사에게 명령을 내리면 아무런 반응이 없게 됩니다.
(2) 대결 대미지
명령을 받은 기사가 다른 기사를 밀치게 되면, 밀려난 기사들은 피해를 입게 됩니다. 이때 각 기사들은 해당 기사가 이동한 곳에서 w×h 직사각형 내에 놓여 있는 함정의 수만큼만 피해를 입게 됩니다. 각 기사마다 피해를 받은 만큼 체력이 깎이게 되며, 현재 체력 이상의 대미지를 받을 경우 기사는 체스판에서 사라지게 됩니다. 단, 명령을 받은 기사는 피해를 입지 않으며, 기사들은 모두 밀린 이후에 대미지를 입게 됩니다. 밀렸더라도 밀쳐진 위치에 함정이 전혀 없다면 그 기사는 피해를 전혀 입지 않게 됨에 유의합니다.
Q 번에 걸쳐 왕의 명령이 주어졌을 때, Q 번의 대결이 모두 끝난 후 생존한 기사들이 총 받은 대미지의 합을 출력하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에 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 개의 명령이 진행된 이후, 생존한 기사들이 총 받은 대미지의 합을 출력합니다.
입출력 예제
예제1
입력:
4 3 3
0 0 1 0
0 0 1 0
1 1 0 1
0 0 2 0
1 2 2 1 5
2 1 2 1 1
3 2 1 2 3
1 2
2 1
3 3
출력:
3
예제 설명
먼저 내가 생각한 것은 아래와 같다.
회사생활하면서 개발을 아예 안한지 좀 많이 시간이 지나다보니, 내가 봐도 터무니없는 생각을 한다 자꾸.
우선 요점은 기사를 이동시켰을 때에 다른 기사의 방패영역과 겹치는지가 가장 중요한 논지라고 생각했다.
따라서 처음 상태의 체스판을 하나 만든다. (기사들이 체스판 위에 없는 상태)
벽과 같은 것은 고려하지 않은 상태에서 기사들의 방패영역이 1로 표시되어 있는 체스판을 하나 만든다.
첫 번째 명령으로 기사를 이동시킨다.
기사의 영역만이 있는 체스판에서 그 영역을 이동시켜서 겹치는 부분은 값이 더해지도록 그란다.
이때 기사들이 있는 위치에 벽이 있는지 확인한다.
벽이 없다면 이번에는 각 기사들의 영역을 확인해서 겹친 부분의 기사가 어느 기사인지 확인한다.
겹친 기사들을 이동시킨다. 이때 기존에 겹쳤던 부분의 값은 다시 1로 바뀌게 된다.
그 이유는 기사들이 출발점에서 영역을 다시 판단하기 때문이다.
그렇게 기사들을 이동시킨 후, 영역 내에 벽이 있는지 확인다.
이 작업을 반복한 후 함정의 위치와 확인해서 기사들이 입는 대지미를 확인하고 체력을 깎는다.
이렇게하면 정말 시뮬레이션 답게 해결할 수는 있겠는데, 불필요한 계산이 너무 많이 들어가고,
기사의 수가 최대 30명이라 시간초과가 발생할 것이다.
결국 BFS를 활용한 문제
해설을 보고 나름대로 정리해보려한다.
확실히 해설에 나와있는 것이 깔끔하다 매우.
나도 코테볼때 이렇게 작성할 수 있으면 좋겠다.
먼저 혼자 생각할 때에 한 기사가 이동했을 때에 그 영역이 두 명의 기사와 겹쳐거 두 기사가 움직여야한다면, 어떤 기사부터 움직여야할지 고민을 했었다.
그런데 생각해보니까 기사의 영역이 직사각형으로 고정이 되었기에, 한 명의 기사가 이동할 때에 두 명의 기사에
영향을 미친다고 하더라도, 결국에 그 영향을 받은 두 기사는 서로 영향을 끼칠 수는 없다.
다만, 그 두 기사로부터 영향을 받을 수 있는 하나의 기사가 있다면 이번에는 어떻게 될까?
사실 이번에도 크게 상관 없다. 왜냐하면 기사가 이동할 수 있는 칸이 단 1칸이기 때문이다.
위의 사진 같은 경우가 있을 수 있어도 여기서 초록색 기사가 먼저 움직이든, 파란색 기사가 먼저 움직이든 그건 상관이 없다.
그리고 큐를 하나 선언해준 다음에, 예를 들어 주황색 기사가 오른쪽으로 하나 움직이라는 명령을 받았다면, 처음에는 큐에 주황색 기사가 들어간다.
그리고 큐에서 꺼내고 한칸 이동시킨다.
그리고 이때에 주황색 기사로 인해 영향을 받는 초록색과 파란색의 기사도 큐에 넣어준다.
큐를 표시하면 위 그림처럼된다.
초록색 기사가 먼저 움직이든 파란색 기사가 먼저 움직이든 상관 없다는 것은
저렇게 큐에 들어가는게 초록색 기사가 먼저 들어가든 파란색 기사가 먼저 들어가든 상관 없다는 뜻이다.
여기서 주의해야할 것은 큐에 들어가는 순간 잠재적으로 이동할 것이라는 것을 표시해줘야한다.
그래야 다시 또 큐에 넣지 않기 때문이다.
하지만 동시에 해당 기사는 큐에서 꺼내지지 않았기에 정말로 기사를 움직이진 않은 상태이다.
여기서 지금 이해가 안가는건, 결국 최종 상태에서 이동이 불가하면 다시 초기화를 해줘야하는데, 그 부분을 찾기가 힘들다.
이 부분은 새로운 배열로 해결한다.
실제 기사들의 위치가 담긴 배열 A가 있다면 위에서 말한 큐에서 이동을 시켜보는 배열.
그러니까 우리가 위 예시를 보았을 때에 머릿속으로 '어.. 이게 이동이 되나..?' 생각하면서 머릿속으로 옮겨보고, 그게 옮겨진다고 생각되면 그때 실제로 이동시키지 않는가?
똑같은 과정이다.
실제 기사들의 위치가 담긴 배열인 A가 있다면, 이번에는 그 기사들의 위치를 복제한 내 머릿속 배열
A`를 만들어준다.
그 A`에서 이동이 불가능하다면 그 상태 그대로 종료가 된다.
결국 실제 위치 A는 그대로이니, 아무것도 달라진 것은 없다.
그런데 A`에서 이동이 가능하다는 결론이 나오면, 이때에 실제 위치를 옮겨준다.
이것이 A`의 값들을 A에 덮어씌우는 과정이다.
지금 설명은 위치만 했지만, 대미지도 동일하게 해준다. 머릿속에서 이동시키고 대미지 계산까지 해놓는 것이다.
이를 반복하면 결국 정답이 나온다.
움직임을 시도하는 함수: tryMovement
이동시키는 함수: movePiece
입력된 명령어를 읽어서 movePiece 함수에 어떤 기사를 어느 방향으로 이동시킬지 전달한다.
movePiece 함수는 전달 받은 기사가 죽은 기사인지 아닌지 판단하고,
죽은 기사가 아니라면 내부에서 tryMovement 함수를 호출해서 이제 머릿속으로 이동이 가능한지 그려보기 시작한다.
tryMovement는 현재 실제 기사의 위치를 가상의 배열로 복사한다.
그리고 movePiece로부터 전달 받은 기사와 이동 방향을 바탕으로 시작한다.
먼저 이동을 하려는 기사를 큐에다가 넣고, 다시 또 큐에 들어가지 않도록 하기 위해서 큐에 들어갔다고 표기한다.
이제 큐에다가 넣은 기사를 큐에서 뽑고 이동이 가능한지 체크한다.
- 영역을 벗어나지 않는지 체크한다.
- 이동하려는 곳에 벽이 있지는 않은지 확인한다.
- 이동하려는 곳에 함정이 있다면 대미지를 계산한다.
- 이동하려는 곳에 다른 기사들이 있는지 확인한다.
여기서 이동하려는 곳에 다른 기사들이 있다면 다른 기사들을 큐에 넣어준다.
단, 이때 이동하려는 곳에 다른 기사들이 있어도 죽은 기사이거나, 이미 큐에 넣었던 기사라면 큐에 넣지 않는다.
위 과정을 큐가 전부 비게 될때까지 반복한다.
그렇게 큐가 비게되거나, 만약 중간에 이동이 불가능하다고 판단이 될 경우,
즉, tryMovement의 결과가 true가 되거나 false가 되거나 두 경우가 있다.
여기서 true가 된다면 이동이 가능한 것이므로 이제 머릿속의 과정을 현실로 옮긴다.
즉, 실제 기사의 위치를 바꾸어주고, 그에 따라 대미지를 계산해준다.
만일 false가 된다면....
아무일도 일어나지 않는다.
머릿속에서 무슨 일이 일어난다고 우리가 머릿속을 다시 되돌리거나 비우기 위해 무슨 과정을 겪지 않지 않는가?
똑같다. true일 때만 무슨 작업을 해주고, false라면 그저 아무일도 일어나지 않는다.
설명이 장황했다.
이제 전체 코드이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.*;
public class CODETREE_The_Royal_Knights_Duel {
// 상수 선언: 기사 최대 개수, 체스판 최대 크기
public static final int MAX_N = 31; // 기사 최대 수
public static final int MAX_L = 41; // 체스판 최대 크기
// 체스판 크기, 기사 수, 명령 수
public static int l, n, q;
// 체스판 정보: 0은 빈칸, 1은 함정, 2는 벽
// 여기서 왜 info를 미리 최대치로 선언하는 것인지 잘 이해가 안간다.
// 하나 생각되는건 일단 이동을 시키고 나서 그게 그 범위 안에 있는 것인지 판단하기 때문인 것 같기도 하다.
public static int[][] info = new int[MAX_L][MAX_L];
// 각 기사의 초기 체력
public static int[] bef_k = new int[MAX_N];
// 각 기사의 위치 (r: 행, c: 열), 크기 (h: 높이, w: 너비), 체력 (k: 체력)
// 이렇게하면 각 배열의 0번부터 1번 기사의 정보, 2번 기사의 정보 이렇게 담기게 된다.
public static int[] r = new int[MAX_N];
public static int[] c = new int[MAX_N];
public static int[] h = new int[MAX_N];
public static int[] w = new int[MAX_N];
public static int[] k = new int[MAX_N];
// 이동 후 위치 nr: 새로운 행
public static int[] nr = new int[MAX_N];
// 이동 후 위치 nc: 새로운 열
public static int[] nc = new int[MAX_N];
// 각 기사가 받은 대미지
public static int[] dmg = new int[MAX_N];
// 각 기사가 이번 턴에 이동했는지를 나타내는 배열
// 이건 왜 필요한건지 잘 모르겠다.
public static boolean[] is_moved = new boolean[MAX_N];
// 상하좌우 방향 벡터
// 알고리즘에서는 평면도가 반대이다.
// x축이 r이고 결국 이게 아래로 내려올수록 커지고, 위로 갈 수록 작아지고, y축이 c이고 이게 왼쪽으로 갈 수록 작아지고 오른쪽으로 갈 수록 커진다.
public static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
// 움직임을 시도하는 함수입니다.
public static boolean tryMovement(int idx, int dir) {
Queue<Integer> q = new LinkedList<>();
boolean is_pos = true; // 초기값은 일단 true로 설정한다.
// 초기화 작업: 각 기사의 대미지와 이동 여부, 새로운 위치를 초기화합니다.
for(int i = 1; i <= n; i++) {
dmg[i] = 0;
is_moved[i] = false;
nr[i] = r[i];
nc[i] = c[i];
}
// 이동을 시도하는 기사를 큐에 추가하고, 이동했음을 표시합니다.
q.add(idx);
is_moved[idx] = true;
// 큐가 빌 때까지 반복합니다.
while(!q.isEmpty()) {
int x = q.poll(); // 큐에서 기사를 하나 꺼냅니다.
// 기사를 이동시킵니다.
nr[x] += dx[dir];
nc[x] += dy[dir];
// 경계를 벗어나는지 체크합니다.
if(nr[x] < 1 || nc[x] < 1 || nr[x] + h[x] - 1 > l || nc[x] + w[x] - 1 > l)
return false; // 체스판을 벗어나면 이동 불가
// 기사가 이동한 위치에서 함정이나 벽에 부딪히는지 확인합니다.
for(int i = nr[x]; i <= nr[x] + h[x] - 1; i++) {
for(int j = nc[x]; j <= nc[x] + w[x] - 1; j++) {
if(info[i][j] == 1) // 함정에 부딪히면 대미지 증가
dmg[x]++;
if(info[i][j] == 2) // 벽에 부딪히면 이동 불가
return false;
}
}
// 다른 기사와 충돌하는지 확인합니다.
for(int i = 1; i <= n; i++) {
// 이미 이동한 기사이거나, 체력이 0 이하인 기사는 무시
if(is_moved[i] || k[i] <= 0)
continue;
// 현재 이동하려는 기사의 영역과 충돌하는 기사가 있는지 확인
if(r[i] > nr[x] + h[x] - 1 || nr[x] > r[i] + h[i] - 1)
continue;
if(c[i] > nc[x] + w[x] - 1 || nc[x] > c[i] + w[i] - 1)
continue;
// 충돌하는 기사가 있으면, 그 기사도 이동시킵니다.
is_moved[i] = true;
q.add(i); // 큐에 추가하여 이동을 처리
}
}
// 이동을 시도한 기사는 대미지를 초기화
dmg[idx] = 0;
return true; // 이동 성공
}
// 특정 기사를 지정된 방향으로 이동시키는 함수입니다.
public static void movePiece(int idx, int dir) {
// 기사가 이미 죽었다면 이동하지 않음
if(k[idx] <= 0) return;
// 이동이 가능한 경우, 실제로 기사를 이동시키고 체력을 업데이트합니다.
if(tryMovement(idx, dir)) {
for(int i = 1; i <= n; i++) {
r[i] = nr[i];
c[i] = nc[i];
k[i] -= dmg[i]; // 대미지를 체력에서 차감
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력값을 받습니다.
l = sc.nextInt(); // 체스판 크기
n = sc.nextInt(); // 기사 수
q = sc.nextInt(); // 명령 수
// 체스판 정보 입력 (0: 빈칸, 1: 함정, 2: 벽)
for(int i = 1; i <= l; i++)
for(int j = 1; j <= l; j++)
info[i][j] = sc.nextInt(); // 위에서 static으로 미리 선언은 해놨다.
// 따라서 여기서 그냥 쓰면 되는데, 덕분에 값이 없는 부분은 영역을 벗어난다고 생각할 수 있게 되었다.
// 각 기사의 초기 정보 입력
for(int i = 1; i <= n; i++) {
// 이 부분은 bufferedReader로 처리할 수 있겠다.
r[i] = sc.nextInt();
c[i] = sc.nextInt();
h[i] = sc.nextInt();
w[i] = sc.nextInt();
k[i] = sc.nextInt();
bef_k[i] = k[i]; // 초기 체력을 저장해 둠
}
// 각 명령에 대해 기사를 이동시킵니다.
for(int i = 1; i <= q; i++) {
int idx = sc.nextInt(); // 명령받은 기사 번호
int dir = sc.nextInt(); // 이동 방향
movePiece(idx, dir); // 기사를 이동시킴
}
// 결과를 계산하고 출력합니다.
long ans = 0; // 총 대미지를 계산하기 위한 변수
for(int i = 1; i <= n; i++) {
if(k[i] > 0) { // 기사가 살아있는 경우
ans += bef_k[i] - k[i]; // 초기 체력에서 현재 체력을 뺀 값을 더함
}
}
System.out.println(ans); // 최종 대미지 합계를 출력
}
}