https://www.acmicpc.net/problem/20056
출처: https://tussle.tistory.com/985
https://developer-u.tistory.com/101
접근 방법
이 문제에 핵심
1. 1번행과 N번 행은 연결, 1번열과 N번 열은 연결되어있습니다.
2. 마법사 상어는 문제의 조건에 맞게 파이어볼을 발사합니다.
3. K번 이동 명령을 진행한 후, 남아있는 파이어볼 질량의 합을 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. K번 이동명령을 진행합니다.
3. 남아있는 파이어볼 질량의 합을 결과로 출력합니다.
파이어볼 이동명령
1번행과 N번 행은 연결, 1번열과 N번열은 연결?
※처음에 이 문장에 대해서 이해하지 못하였지만 예제입력을 시뮬레이션 돌려보면서 이해가 되었습니다.
| 파이어볼(↓) |
위에 표에서 파이어볼이 4번 방향으로 1칸 이동할 때 결과
| 파이어볼 | ||
칸을 이동할 때 범위를 넘어가면 다시 1이나 N으로 반복되는 것을 뜻합니다.
파이어볼 이동방향
| 7(-1, -1) | 0(-1, 0) | 1(-1, 1) |
| 6(0, -1) | 파이어볼 | 2(0, 1) |
| 5(1, -1) | 4(1, 0) | 3(1, 1) |
방향을 변경값을 표현하는 배열
dr[] = {-1, -1, 0, 1, 1, 1, 0, -1}
dc[] = {0, 1, 1, 1, 0, -1, -1, -1}
이동 순서.
1. 모든 파이어볼 속도(s)와 방향(d)에 맞게 이동합니다.
2. 파이어볼 2개 이상있는 칸 조건에 맞게 분열 진행!
1) 나눠질 때 질량 : 질량의 합 / 5
2) 나눠질 때 속도 : 속도의 합 / 파이어볼 개수
3) 나눠질 때 방향 : 모든 방향이 홀수이거나 짝수일 때 {0, 2, 4, 6}, 아닐 때 {1, 3, 5, 7}
※저는 문제를 잘못 해석해서 분열된 파이어볼을 이동하는 것처럼 구현해서 시간 낭비를 했습니다 ㅠ^ㅠ 파이어볼 방향만 바뀝니다!
예제입력 3.
1. 입력된 정보를 저장합니다.
N : 4
M : 2
K : 3
초기 파이어볼 정보
| {5, 2, 2} | {7, 1, 6} | ||
2. K번 이동명령을 진행합니다.
1번째 이동명령 진행!
| {5, 2, 2}, {7, 1, 6} | |||
분열 진행!
분열될 질량 : 12 / 5 = 2
분열될 속도 : 3 / 2= 1
분열될 방향 : {2, 6} 모두 짝수 = {0, 2, 4, 6}
분열 완료!
| {2, 1, 0}, {2, 1, 2}, {2, 1, 4}, {2, 1, 6} | |||
2번째 이동명령 진행!
| {2, 1, 6} | {2, 1, 2} | ||
| {2, 1, 4} | |||
| {2, 1, 0} |
분열할 파이어볼 존재 X
3번째 이동명령 진행!
| {2, 1, 6}, {2, 1, 2} | |||
| {2, 1, 4}, {2, 1, 0} | |||
(1, 1) 분열 진행!
분열될 질량 : 4 / 5 =0
분열될 질량이 0이므로 분열 종료!
(3, 3) 분열 진행!
분열될 질량 : 4 / 5 =0
분열될 질량이 0이므로 분열 종료!
분열 완료!
3. 남아있는 파이어볼 질량의 합을 결과로 출력합니다.
남아있는 파이어볼 개수 : 0개
0을 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 파이어볼들의 정보를 띄어쓰기 기준 나누었습니다.
- K번 meteorMove와 meteorFire를 실행하여 모든 파이어볼 이동과 분열을 진행합니다.
- meteorCal을 실행하여 남은 파이어볼 질량의 합을 결과로 BufferedWriter에 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- meteorMove함수는 파이어볼의 이동을 진행합니다.
- meteorFire함수는 2개 이상의 파이어볼이 같이 있으면 분열을 진행합니다.
- meteorCal함수는 남은 파이어볼 질량의 합을 구합니다.
소중한 나의 정리
맵상에 존재하는 파이어볼정보, 각각의 격자의 위치로 이동한 파이어볼에 대한 정보를 유지하는 2차원 구조체 배열 필요함(ArrayList<Fireball>[][]map).
위의 2차원 구조체 배열과는 별개로 존재하는 모든 파이어볼에 대한 정보를 유지하는 자료구조 필요함(ArrayList<Fireball> fireballs).
기본적으로 처음시작할때 map에는 아무것도없고 오직 파이어볼에 대한 정보를 알려주는 fireballs에만 파이어볼이 있다. 그 후 이동을 할시 map에 파이어볼에 관한 정보가 생긴다. 이후 각map의 각 격자를 뒤져 2개이상이면 분할을 하는데 분할을 당하는 파이어볼은 fireballs, map두 자료구조에서 모두 없어진다. 분할되어 새로 생성된 파이어볼은 fireballs에만 존재하고 아직 map에는 표시하지 않는다. 다음이동 시에 표시한다.
"당위적으로 생각해보자. 왜 fireballs라는 자료구조가 필요하나? 주인공이 파이어볼이므로 파이어볼을 관리할 자료구조가 필요하다고 생각할 수 있다. 그리고 그 자료구조는 어떤 순서에 상관없이(파이어볼의 위치정보가 있지만 그것은 구조체 안에 들어가있는 정보다)보관되어도 되므로 Set을 쓸수 있다(답지는 ArrayList를 사용했으니 내가 직접Set을 사용해 볼것).
왜 2차원 구조체 배열 자료구조가 필요할까? 파이어볼이 합쳐지고 분열하여 흩어지고 난리부르스 치는 이동하는 파이어볼을 관리해야 하므로."
==> 이후 난리부르스치는 파이어볼을 어떻게 자료구조에 차곡차곡 관리할지는 구현력에 해당하는 것이다. 절차를 잘 구현해야 한다. 위에서 언급한 이런것들이 진정한 구조화 능력, 구현능력임!!
이동한다(이동한 격자에맞는 map의 인덱스에 파이어볼이 담긴다) -> 분열한다(격자에 있는 파이어볼중 그갯수가 1개면 map자료구조에서는 없어진다. 왜? map은 오직 이동하는 파이어볼만 관리하므로. 2개면 각각의 파이어볼이 갖는 세부값들을 합산하여 계산하면서 map자료구조에서 없앤다. 왜? 마찬가지로 map은 오직 이동하는 파이어볼만 관리하므로 이동에 필요한 알맹이만 챙기고 map은 다시 새것처럼 보존시켜 주어야 하기 때문이다.그리고 fireballs에서도 없앤다. 왜? 분열하여 없어진것과 같으므로. 대신 새롭게 분열되어 생성된 파이어볼을 fireballs에 담는다. 이렇게 새롭게 분열하여 생성된 파이어볼은 fireballs에만 존재하고 map에는 아직 존재하지 않는상태가 된다. 즉 분열이 모두 끝나면 map은 비어있다.)
단순하게 보면 위처럼 이동, 분열과정을 반복하는 것이다. 내가 익힐것은 객체의 이동에 주안점을 둔 문제에서 주인공객체가 이동하면 그 이동을 관리하는 자료구조(map)를 따로 만들고 이동과 별개로 전체 객체를 관리하는 자료구조를 따로 두어야 한다는 것이다.
결과코드
import java.sql.Array;
import java.util.*;
import java.io.*;
public class Main {
//파이어볼 정보 클래스
static class meteor{
int r, c, m, s, d;
public meteor(int r, int c, int m, int s, int d){
this.r = r;
this.c = c;
this.m = m;
this.s = s;
this.d = d;
}
}
static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1}; //방향 r값 변경값
static int[] dc = {0, 1, 1, 1, 0, -1, -1, -1}; //방향 c값 변경값
static ArrayList<meteor>[][] map; //맵상에 존재하는 파이어볼정보. 각각의 격자의 위치로 이동한 파이어볼에 대한 정보를 유지
static ArrayList<meteor> meteors = new ArrayList<>(); //존재하는 모든 파이어볼에 대한 정보
//기본적으로 처음시작할때 map에는 아무것도없고 오직 파이어볼에 대한 정보를 알려주는 meteors에만 파이어볼이 있다. 그 후 이동을 할시
//map에 파이어볼에 관한 정보가 생긴다. 이후 각map의 각 격자를 뒤져 2개이상이면 분할을 하는데 분할을 당하는 파이어볼은 meteors, map두 자료구조에서 모두
//없어진다. 분할되어 새로 생성된 파이어볼은 meteors에만 존재하고 아직 map에는 표시하지 않는다. 다음이동 시에 표시한다.
/*
맵상에 존재하는 파이어볼정보, 각각의 격자의 위치로 이동한 파이어볼에 대한 정보를 유지하는 2차원 구조체 배열 필요함(ArrayList<Fireball>[][]map).
위의 2차원 구조체 배열과는 별개로 존재하는 모든 파이어볼에 대한 정보를 유지하는 자료구조 필요함(ArrayList<Fireball> fireballs).
기본적으로 처음시작할때 map에는 아무것도없고 오직 파이어볼에 대한 정보를 알려주는 fireballs에만 파이어볼이 있다. 그 후 이동을 할시
map에 파이어볼에 관한 정보가 생긴다. 이후 각map의 각 격자를 뒤져 2개이상이면 분할을 하는데 분할을 당하는 파이어볼은 fireballs, map두 자료구조에서 모두
없어진다. 분할되어 새로 생성된 파이어볼은 fireballs에만 존재하고 아직 map에는 표시하지 않는다. 다음이동 시에 표시한다.
당위적으로 생각해보자. 왜 fireballs라는 자료구조가 필요하나? 주인공이 파이어볼이므로 파이어볼을 관리할 자료구조가 필요하다고 생각할 수 있다. 그리고 그 자료구조는
어떤 순서에 상관없이(파이어볼의 위치정보가 있지만 그것은 구조체 안에 들어가있는 정보다)보관되어도 되므로 Set을 쓸수 있다(답지는 ArrayList를 사용했으니 내가 직접Set을 사용해 볼것).
왜 2차원 구조체 배열 자료구조가 필요할까? 파이어볼이 분열하고 흩어지고 난리부르스 치는 이동하는 파이어볼을 관리해야 하므로.
==> 이후 난리부르스치는 파이어볼을 어떻게 자료구조에 차곡차곡 관리할지는 구현력에 해당하는 것이다. 절차를 잘 구현해야 한다.
이동한다(이동한 격자에맞는 map의 인덱스에 파이어볼이 담긴다) -> 분열한다(격자에 있는 파이어볼중 그갯수가 1개면 map자료구조에서는 없어진다. 왜? map은 오직 이동하는 파이어볼만 관리하므로.
2개면 각각의 파이어볼이 갖는 세부값들을 합산하여 계산하면서 map자료구조에서 없앤다. 왜? 마찬가지로 map은 오직 이동하는 파이어볼만 관리하므로 이동에 필요한 알맹이만 챙기고
map은 다시 새것처럼 보존시켜 주어야 하기 때문이다.그리고 fireballs에서도 없앤다. 왜? 분열하여 없어진것과 같으므로. 대신 새롭게 분열되어 생성된 파이어볼을 fireballs에 담는다.
이렇게 새롭게 분열하여 생성된 파이어볼은 fireballs에만 존재하고 map에는 아직 존재하지 않는상태가 된다. 즉 분열이 모두 끝나면 map은 비어있다.)
단순하게 보면 위처럼 이동, 분열과정을 반복하는 것이다. 내가 익힐것은 객체의 이동에 주안점을 둔 문제에서 주인공객체가 이동하면 그 이동을 관리하는 자료구조(map)를 따로 만들고 이동과 별개로 전체 객체를
관리하는 자료구조를 따로 두어야 한다는 것이다.
*/
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
map = new ArrayList[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
map[i][j] = new ArrayList<>();
}
//입력되는 파이어볼 정보 저장
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
int m = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
meteors.add(new meteor(r, c, m, s, d));
}
//K번 이동명령 진행
for (int i = 0; i < K; i++) {
meteorMove(N);
meteorFire(N);
}
bw.write(meteorCal() + ""); //메테오 질량의 합 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
//파이어볼 이동시키는 함수
static void meteorMove(int N) {
for (meteor cur : meteors) {
//r, c값 변경
// +N을 하는 이유는 이동하였을 때 음수가 나올 수 있기 때문입니다.
int tempR = (cur.r + N + dr[cur.d] * (cur.s%N)) % N;
int tempC = (cur.c + N + dc[cur.d] * (cur.s%N)) % N;
cur.r = tempR;
cur.c = tempC;
//이동한 파이어볼 저장
map[cur.r][cur.c].add(cur);
}
}
//파이어볼 분열 진행
static void meteorFire(int N){
for(int r = 0; r<N;r++){
for(int c = 0; c<N;c++) {
//파이어볼 개수가 2개 미만일 때
if(map[r][c].size() < 2){
map[r][c].clear();//어차피 모든 파이어볼에 대한 정보는 meteors에 저장되므로 여기서 map을 clear해도 상관없음.
continue;
}
//파이어볼 2개 이상일 때
int mSum = 0, sSum = 0, oddCount = 0, evenCount = 0;
int size = map[r][c].size();
//분열 진행!
for(meteor cur : map[r][c]){
mSum += cur.m; //질량 더하기
sSum += cur.s; //속도 더하기
if(cur.d % 2 == 1) //방향 홀수일 때
oddCount++;
else //방향 짝수일 때
evenCount++;
meteors.remove(cur); //분열될 파이어볼 제거!
}
map[r][c].clear();
mSum /= 5; //분열될 질량 구하기
if(mSum == 0) //분열될 질량이 0이면 분열 실패!
continue;
sSum /= size; //분열될 속도 구하기
//모든 파이어볼 방향이 짝수이거나 홀수일 때
if(oddCount == size || evenCount == size){
for(int i=0;i<8;i+=2) //{0, 2, 4, 6} 방향 분열
meteors.add(new meteor(r,c,mSum, sSum, i));
}else{
for(int i=1;i<8;i+=2) //{1, 3, 5, 7} 방향 분열
meteors.add(new meteor(r,c,mSum, sSum, i));
}
}
}
}
//파이어볼 질량의 합 구하는 함수
static int meteorCal(){
int result = 0;
//모든 질량 더하기!
for(meteor cur : meteors)
result += cur.m;
return result;
}
}
23.12.22. 좀 더 의미있는 주석을 단 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
/*
맵상에 존재하는 파이어볼정보, 각각의 격자의 위치로 이동한 파이어볼에 대한 정보를 유지하는 2차원 자료구조 배열 필요함(ArrayList<Fireball>[][]map).
위의 2차원 구조체 배열과는 별개로 존재하는 모든 파이어볼에 대한 정보를 유지하는 자료구조 필요함(ArrayList<Fireball> fireballs).
기본적으로 처음시작할때 map에는 아무것도없고 오직 파이어볼에 대한 정보를 알려주는 fireballs에만 파이어볼이 있다. 그 후 이동을 할시
map에 파이어볼에 관한 정보가 생긴다. 이후 각map의 각 격자를 뒤져 2개이상이면 분할을 하는데 분할을 당하는 파이어볼은 fireballs, map두 자료구조에서 모두
없어진다. 분할되어 새로 생성된 파이어볼은 fireballs에만 존재하고 아직 map에는 표시하지 않는다. 다음이동 시에 표시한다.
당위적으로 생각해보자. 왜 fireballs라는 자료구조가 필요하나? 주인공이 파이어볼이므로 파이어볼을 관리할 자료구조가 필요하다고 생각할 수 있다. 그리고 그 자료구조는
어떤 순서에 상관없이(파이어볼의 위치정보가 있지만 그것은 구조체 안에 들어가있는 정보다)보관되어도 되므로 Set을 쓸수 있지 않을까 생각할 수도 있지만 fireballs자료구조안에 반복문을 통해
하나하나 꺼내는 과정이 들어가 있으므로 리스트 자료구조를 사용하는 것이 자연습럽다.
왜 2차원 구조체 배열 자료구조가 필요할까? 파이어볼이 분열하고 흩어지고 난리부르스 치는 이동하는 파이어볼을 관리해야 하므로.
==> 이후 난리부르스치는 파이어볼을 어떻게 자료구조에 차곡차곡 관리할지는 구현력에 해당하는 것이다. 절차를 잘 구현해야 한다.
이동한다(이동한 격자에맞는 map의 인덱스에 파이어볼이 담긴다) -> 분열한다(격자에 있는 파이어볼중 그 갯수가 1개면 map자료구조에서는 없어진다. 왜? map은 오직 이동하는 파이어볼만 관리하므로.
2개면 각각의 파이어볼이 갖는 세부값들을 합산하여 계산하면서 map자료구조에서 없앤다. 왜? 마찬가지로 map은 오직 이동하는 파이어볼만 관리하므로 이동에 필요한 알맹이만 챙기고
map은 다시 새것처럼 보존시켜 주어야 하기 때문이다.그리고 fireballs에서도 없앤다. 왜? 분열하여 없어진것과 같으므로. 대신 새롭게 분열되어 생성된 파이어볼을 fireballs에 담는다.
매번 이중반복문을 돌면서 map에 있는 파이어볼은 모두 삭제 되지만 fireballs에서는 그대로 남는 것과 삭제되는 것이있다. fireballs에서는 오직 융합하여 분열이 가능한 융합에 사용된 파이어볼만 삭제된다.
이렇게 새롭게 분열하여 생성된 파이어볼은 fireballs에만 존재하고 map에는 아직 존재하지 않는상태가 된다. 즉 분열이 모두 끝나면 map은 비어있다.)
단순하게 보면 위처럼 이동, 분열과정을 반복하는 것이다. 내가 익힐것은 객체의 이동에 주안점을 둔 문제에서 주인공객체가 이동하면 그 이동을 관리하는 자료구조(map)를 따로 만들고 이동과 별개로 전체 객체를
관리하는 자료구조를 따로 두어야 한다는 것이다.
*/
public class Testing3 {
static class Meteor {
int r;
int c;
int m;
int s;
int d;
public Meteor(int r, int c, int m, int s, int d) {
this.r = r;
this.c = c;
this.m = m;
this.s = s;
this.d = d;
}
}
public static List<Meteor>[][] map;
public static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
public static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
map = new ArrayList[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = new ArrayList<>();
}
}
List<Meteor> meteors = new ArrayList<>();
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken())-1;
int mm = Integer.parseInt(st.nextToken());
int ss = Integer.parseInt(st.nextToken());
int dd = Integer.parseInt(st.nextToken());
meteors.add(new Meteor(r, c, mm, ss, dd));
}
for (int i = 0; i < k; i++) {
moveMeteor(meteors, n);
fireMeteor(meteors, n);
}
int answer = getTotalWeight(meteors);
System.out.println(answer);
}
//r,c,m,s,d
public static void moveMeteor(List<Meteor> meteors, int n) {
for (var meteor : meteors) {
int nr = (meteor.r + n + (dy[meteor.d] * meteor.s)% n ) % n;
int nc = (meteor.c + n + (dx[meteor.d] * meteor.s% n)% n ) % n;
meteor.r = nr;
meteor.c = nc;
map[nr][nc].add(meteor);
}
}
public static void fireMeteor(List<Meteor> meteors, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int size = map[i][j].size();
//1개의 파이어볼을 가지고 있는 좌표는 그 파이어볼을 좌표에서는 삭제하지만 파이어볼리스트에는 남겨 놓아야 다음 움직임에서
//좌표로 던져질 수 있다.
if (size < 2) {
map[i][j].clear();
continue;
}
int mSum = 0, sSum = 0, oddCount = 0, evenCount = 0;
//융합의 for문
for (var fireball : map[i][j]) {
mSum += fireball.m;
sSum += fireball.s;
if (fireball.d % 2 == 0)
++evenCount;
else
++oddCount;
//융합에서는 기존의 파이어볼이 없어지는 것으로 좌표,파이어볼 리스트 둘 모두에서 삭제되어야 한다.
meteors.remove(fireball);
}
map[i][j].clear();
int nm = mSum / 5;
if (nm == 0)
continue;
int ns = sSum / size;
//구조화 사고가 정말 중요하다. 세부적이고 첨예한 과정에서 어떠한 자료구조에는 데이터를 남기고 어떠한 자료구조에서는 데이터를
//삭제할 것인지, 또 어떠한 자료구조에 데이터를 추가해 줄 것인지를 전체 흐름을 염두하면서 코딩해야 한다.
if (evenCount == size || oddCount == size) {
for (int k = 0; k <= 6; k += 2)
//다음 움직임에서 뿌려지기 위해 새로이 생겨나는 파이어볼은 파이어볼 리스트에 추가해 주고 다음 움직임에서 좌표로 뿌려진다.
meteors.add(new Meteor(i, j, nm, ns, k));
} else
for (int k = 1; k <= 7; k += 2)
meteors.add(new Meteor(i, j, nm, ns, k));
}
}
}
public static int getTotalWeight(List<Meteor> meteors) {
int sum = 0;
for (var meteor : meteors)
sum += meteor.m;
return sum;
}
}'알고리즘 > 구현' 카테고리의 다른 글
| 백준(BOJ) 20546: 🐜 기적의 매매법 🐜 (0) | 2023.11.16 |
|---|---|
| 백준(BOJ) 21608 : 상어 초등학교 (0) | 2023.11.15 |
| 백준(BOJ) 16918번 봄버맨 (0) | 2023.07.18 |