Life Engineering
[BOJ 21611] 마법사 상어와 블리자드 (Java) 본문
https://www.acmicpc.net/problem/21611
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_BOJ_21611 {
static int N, M;
static int[][] map;
static int d, s;
static int one=0, two=0, three=0;
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());
map=new int[N+1][N+1];
for (int i=1; i<=N; i++) {
st=new StringTokenizer(br.readLine());
for (int j=1; j<=N; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
for (int i=0; i<M; i++) {
st=new StringTokenizer(br.readLine());
d=Integer.parseInt(st.nextToken());
s=Integer.parseInt(st.nextToken());
dropIce(d, s);
move(gather());
while (explode()) {
move(gather());
}
change();
}
System.out.println((1*one)+(2*two)+(3*three));
}
private static void dropIce(int d, int s) {
int[] dy= {0, -1, 1, 0, 0};
int[] dx= {0, 0, 0, -1, 1};
int r=(N+1)/2, c=(N+1)/2;
for (int i=0; i<s; i++) {
r+=dy[d];
c+=dx[d];
map[r][c]=0;
}
}
private static void move(ArrayList<Integer> li) {
int[][] tempMap=new int[N+1][N+1];
int[] dy= {0,1,0,-1};
int[] dx= {-1,0,1,0};
int r=(N+1)/2, c=(N+1)/2;
int len=1;
int d=0;
int cnt=0;
while (len<N) {
int repeat = len==N-1?3:2;
for (int j=0; j<repeat; j++) {
for (int i=0; i<len; i++) {
r+=dy[d];
c+=dx[d];
while (cnt<li.size() && li.get(cnt)==0) cnt+=1;
if (cnt<li.size()) tempMap[r][c]=li.get(cnt++);
}
d=(d+1)%4;
}
len++;
}
map=tempMap;
}
public static ArrayList<Integer> gather() {
int[] dy= {0,1,0,-1};
int[] dx= {-1,0,1,0};
int r=(N+1)/2, c=(N+1)/2;
int len=1;
int d=0;
ArrayList<Integer> li=new ArrayList<>();
while (len<N) {
int repeat = len==N-1?3:2;
for (int j=0; j<repeat; j++) {
for (int i=0; i<len; i++) {
r+=dy[d];
c+=dx[d];
li.add(map[r][c]);
}
d=(d+1)%4;
}
len++;
}
return li;
}
private static boolean explode() {
int[] dy= {0,1,0,-1};
int[] dx= {-1,0,1,0};
int r=(N+1)/2, c=(N+1)/2;
int len=1;
int d=0;
int val=-1;
ArrayList<int[]> balls=new ArrayList<>();
boolean isExplode=false;
while (len<N) {
int repeat = len==N-1?3:2;
for (int j=0; j<repeat; j++) {
for (int i=0; i<len; i++) {
r+=dy[d];
c+=dx[d];
if (val!=map[r][c]) {
if (balls.size()>=4) {
isExplode=true;
for (int[] pos : balls) {
map[pos[0]][pos[1]]=0;
if (val==1) one++;
else if (val==2) two++;
else three++;
}
}
val=map[r][c];
balls.clear();
}
balls.add(new int[] {r,c});
}
d=(d+1)%4;
}
len++;
}
return isExplode;
}
private static void change() {
int[] dy= {0,1,0,-1};
int[] dx= {-1,0,1,0};
int r=(N+1)/2, c=(N+1)/2;
int len=1;
int d=0;
int val=-1;
int cnt=0;
ArrayList<Integer> groups=new ArrayList<>();
while (len<N) {
int repeat = len==N-1?3:2;
for (int j=0; j<repeat; j++) {
for (int i=0; i<len; i++) {
r+=dy[d];
c+=dx[d];
if (val!=map[r][c]) {
if (cnt>0) {
groups.add(cnt);
groups.add(val);
}
val=map[r][c];
cnt=0;
}
cnt++;
}
d=(d+1)%4;
}
len++;
}
move(groups);
}
}
푼 방식이 마음에 들지 않는다.. 중복되는 코드도 너무 많고..
map과 map의 요소를 저장하는 list를 왔다갔다 할 필요 없이, 애초에 구슬을 던질 때만 list, map을 연결시켜주고
그 밖의 과정들은 모두 list에서 처리하는게 효율성이 좋겠다.
아래 코드는 list를 사용해서 수정한 코드..
이 문제에서 유의할 점은 맨 마지막 번째에서 비로소 그룹이 되거나/폭발하는 case가 될 경우가 있기 때문에 이 경우를 놓쳐주지 않기 위해 map의 모든 항목에 대해서 체크가 끝나도 한번 더 count를 체크해줘야 한다는 점이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_BOJ_21611 {
static int N, M;
static int[][] map;
static int d, s;
static int one=0, two=0, three=0;
static ArrayList<Integer> list;
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());
map=new int[N+1][N+1];
for (int i=1; i<=N; i++) {
st=new StringTokenizer(br.readLine());
for (int j=1; j<=N; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
for (int i=0; i<M; i++) {
st=new StringTokenizer(br.readLine());
d=Integer.parseInt(st.nextToken());
s=Integer.parseInt(st.nextToken());
dropIce(d, s);
list=move(); //map=>list
explode();
change();
//System.out.println(list);
update(); //list=>map
}
System.out.println((1*one)+(2*two)+(3*three));
}
private static void dropIce(int d, int s) {
int[] dy= {0, -1, 1, 0, 0};
int[] dx= {0, 0, 0, -1, 1};
int r=(N+1)/2, c=(N+1)/2;
for (int i=0; i<s; i++) {
r+=dy[d];
c+=dx[d];
map[r][c]=0;
}
}
private static ArrayList<Integer> move() {
ArrayList<Integer> li=new ArrayList<>();
int[] dy= {0,1,0,-1};
int[] dx= {-1,0,1,0};
int r=(N+1)/2, c=(N+1)/2;
int len=1;
int d=0;
while (len<N) {
int repeat = len==N-1?3:2;
for (int j=0; j<repeat; j++) {
for (int i=0; i<len; i++) {
r+=dy[d];
c+=dx[d];
if (map[r][c]!=0) li.add(map[r][c]);
}
d=(d+1)%4;
}
len++;
}
return li;
}
private static void explode() {
while (true) {
ArrayList<Integer> temp=new ArrayList<>();
boolean isExplode=false;
int value=-1;
int cnt=0;
for (int i=0; i<list.size(); i++) {
int num=list.get(i);
temp.add(num);
if (value!=num) {
if (cnt>=4) {
isExplode=true;
for (int j=0; j<cnt+1; j++) {
temp.remove(temp.size()-1);
}
temp.add(num);
if (value==1) one+=cnt;
else if (value==2) two+=cnt;
else three+=cnt;
}
value=num;
cnt=1;
}
else cnt++;
}
if (cnt>=4) {
for (int j=0; j<cnt; j++) {
temp.remove(temp.size()-1);
}
if (value==1) one+=cnt;
else if (value==2) two+=cnt;
else three+=cnt;
}
if (!isExplode) break;
list=temp;
}
}
private static void change() {
ArrayList<Integer> temp=new ArrayList<>();
int val=-1;
int cnt=0;
for (int i=0; i<list.size(); i++) {
int num=list.get(i);
if (val!=num) {
if (cnt>0) {
temp.add(cnt);
temp.add(val);
}
val=num;
cnt=1;
}
else {
cnt++;
}
}
if (cnt>0) {
temp.add(cnt);
temp.add(val);
}
list=temp;
}
private static void update() {
int[] dy= {0,1,0,-1};
int[] dx= {-1,0,1,0};
int r=(N+1)/2, c=(N+1)/2;
int len=1;
int d=0;
int cnt=0;
while (len<N) {
int repeat = len==N-1?3:2;
for (int j=0; j<repeat; j++) {
for (int i=0; i<len; i++) {
r+=dy[d];
c+=dx[d];
if (cnt<list.size()) map[r][c]=list.get(cnt++);
else map[r][c]=0;
}
d=(d+1)%4;
}
len++;
}
}
}
'Problem Solving' 카테고리의 다른 글
[BOJ 9205] 맥주 마시면서 걸어가기 (Java) (0) | 2022.04.13 |
---|---|
[BOJ 17143] 낚시왕 (Java) (0) | 2022.04.13 |
[SWEA 4013] 특이한 자석 (Java) (0) | 2022.04.13 |
[SWEA 5604] 구간 합 (Java) (0) | 2022.04.13 |
[SWEA 9760] Poker Game (Java) (0) | 2022.04.12 |