📝 문제
💡 풀이 과정
⛓ 사용한 자료구조 : 우선순위 큐
문제에서 제시한 규칙에 따라 충실하게 구현하는 시뮬레이션 문제이다. 이런 유형의 문제를 풀 때는 문제를 풀면서 중간중간 디버깅을 진행해주는 것이 좋다. 코드를 모두 작성하고 나서 오류를 잡아내려면 작성한 코드를 하나하나 되짚어보는 수 밖에 없기 때문이다.
Gem 클래스
각 맵에 있는 구슬의 번호, 방향, 무게를 모두 기억해줘야 하기 때문에 이러한 구슬 정보를 저장할 Gem 클래스를 만들어 사용했다. 앞서 언급한 구슬 정보 외에도 구슬의 위치를 추가로 저장하고 구슬의 번호를 내림차순으로 정렬하기 위해 compareTo 메소드를 오버라이드했는데, 이유는 아래 설명을 참고하기!
아이디어
매 t 시간마다 해야 할 행동은 크게 두 가지이다.
- 구슬 이동 or 방향 전환
- 겹치는 구슬 정보 갱신
이를 위해서는 맵의 각 위치에 여러 구슬이 위치하게 될 경우 구슬 정보를 모아 새로운 구슬 정보를 등록해줘야 한다. 이를 위해서는 구슬을 이동시킬 때마다 겹치는지를 검사하여 갱신해주는 방법이 있고, 구슬을 모두 이동시킨 후에 한번에 갱신하는 방법이 있는데, 이 중 후자를 선택했다.
전체적인 코드의 흐름은 다음과 같다.
- 구슬 이동 or 방향전환
- 맵에 있는 구슬의 이동 방향대로 구슬의 위치를 갱신한다. 이 때 구슬이 맵을 벗어나는 경우엔 방향만 전환한다.
- 갱신한 구슬 정보를 맵이 아닌 임시 큐에 넣어둔다.
- 모든 구슬 정보를 갱신했다면 맵에 구슬 정보들을 넣어준다.
- 겹치는 구슬 정보 갱신
- 각 맵을 순회하며 하나의 위치에 구슬이 여러 개 존재할 경우 해당 구슬들을 모아 새로운 구슬 정보를 만든다.
- 새로운 구슬 정보를 현재 위치에 등록한다.
이를 위해 2차원 형태의 맵에 각각 우선순위 큐를 생성하여 3차원 맵을 만들었다. 이렇게 하면 앞서 구슬 클래스에 오버라이드한 compareTo 에 의해 구슬이 겹칠 경우 번호가 가장 높은 구슬이 가장 앞쪽에 위치하게 되어 따로 구슬의 번호를 비교해주는 작업을 진행하지 않아도 된다.
또한 구슬의 위치를 갱신할 때는 모든 구슬의 이동을 일괄처리해야 한다. 하나씩 이동시키면 맵을 탐색할 때 현재 구슬이 이동 전 구슬인지 이동 후 구슬인지 알 수 없기 때문이다. 따라서 새로 이동할 좌표를 해당 구슬 클래스 내 변수로 저장하고( i , j ), 이 구슬들을 임시 큐에 저장두었다가 한 번에 맵에 등록하는 과정을 거쳤다.
사용한 함수
-
move()구슬을 이동시키는 함수이다. 앞서 설명한 구슬의 이동 및 방향 전환을 담당한다.
-
rotate()구슬의 방향을 컨트롤하는 델타 배열을 2차원이 아닌 1차원의
di,dj배열로 사용했기 때문에, 각 구슬의 방향을 조건문으로 처리해줘야 한다. 굳이 함수로 빼지 않아도 되는데 가독성을 위해 따로 분리했다. -
merge()한 위치에 있는 여러 구슬을 합쳐 새로운 구슬 정보를 맵에 등록하는 함수이다. 앞서 맵을 우선순위 큐로 만들고 구슬의 번호를 기준으로 내림차순 정렬하도록 설정했기 때문에, 가장 앞의 구슬 번호와 방향을 토대로 구슬 무게의 합을 구해 새로운 구슬 정보를 생성한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N,M,T;
static PriorityQueue<Gem>[][] map;
static int[] di = {-1,1,0,0}; //U-D-L-R
static int[] dj = {0,0,-1,1};
static void merge() {
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(map[i][j].size()>1) { //구슬이 겹쳐지는 경우
Gem bigNum = map[i][j].poll(); //번호가 가장 높은 구슬
int sum=bigNum.w;
for(int q=0,size=map[i][j].size();q<size;q++) {
sum+=map[i][j].poll().w;
}
map[i][j].offer(new Gem(i,j,bigNum.n, bigNum.d, sum));
}
}
}
}
static int rotate(int d) {
if(d==0) return 1;
if(d==1) return 0;
if(d==2) return 3;
return 2;
}
static void move() {
Queue<Gem> q = new LinkedList<>();
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(map[i][j].size()>0) {
Gem tmp = map[i][j].poll();
int td = tmp.d;
int ni = i+di[td];
int nj = j+dj[td];
if(ni<0 || ni>=N || nj<0 || nj>=N) { //방향 회전
tmp.d = rotate(td);
q.offer(tmp);
continue;
}
tmp.i=ni;
tmp.j=nj;
q.offer(tmp);
}
}
}
//이동이 끝나면 맵에 반영
while(!q.isEmpty()) {
Gem tmp = q.poll();
map[tmp.i][tmp.j].offer(tmp);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
map = new PriorityQueue[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
map[i][j] = new PriorityQueue<>();
}
}
for(int m=0;m<M;m++) {
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken())-1;
int j = Integer.parseInt(st.nextToken())-1;
String d = st.nextToken();
int dir=0;
if(d.equals("D")) dir=1;
else if(d.equals("L")) dir=2;
else if(d.equals("R")) dir=3;
int w = Integer.parseInt(st.nextToken());
map[i][j].offer(new Gem(i,j,m,dir,w));
}
for(int t=0;t<T;t++) {
move();
merge();
}
int max=0,cnt=0;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(map[i][j].size()>0) {
max = Math.max(map[i][j].poll().w, max);
cnt++;
}
}
}
System.out.println(cnt+" "+max);
}
static class Gem implements Comparable<Gem> {
int i,j,n,d,w;
public Gem(int i, int j, int n, int d, int w) {
this.i = i;
this.j = j;
this.n = n;
this.d = d;
this.w = w;
}
@Override
public int compareTo(Gem o) {
return o.n-this.n;
}
}
}