[문제]
https://www.acmicpc.net/problem/21610
21610번: 마법사 상어와 비바라기
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기
www.acmicpc.net
[풀이과정]
문제를 요약하자면 다음과 같다.
1. 맨 처음으로 비바라기를 시전하여 (N,1) , (N-2) , (N-1,1),(N-1,2) 비 구름을 만든다.
(반복과정 2~5)
2. 모든 구름의 위치를 d방향으로 s칸 이동시킨다. 이동 후의 구름의 위치의 바구니 칸에 물의 양을 1 증가 시킨다.
-이 때 신경써야 할 부분은 1번행과 N번 행이 연결되어 있고 1번 열과 N번 열이 연결되어있어 1에서 N으로 , N 에서 1로 경계를 넘어 이동 할 수 있다는 점이다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 바구니 칸을 기준으로 거리가 1인 대각선 위치의 물이 있는 바구니 수만큼 바구니의 물의 양이 증가한다.
-여기선 경계를 넘어가는 칸은 세어주지않는다.
5. 3에서 구름이 사라진 위치를 제외하고 바구니에 저장된 물의 양이 2이상인 모든 칸에 구름이 생기고 , 물의 양은 2 줄인다.
문제에서 주어지는 이동 회수 만큼 이동이 끝나고 바구니에 들어있는 물의 양의 총 합을 구하면된다.
[변수 선언]
map[r][c] : 바구니에 저장된 물의 양
cloud[r][c]: 이동시켜야 하는 구름의 존재 유무
copyCloud[r][c]: 3에서 구름이 사라진 위치 체크
static int[][] map ;
static boolean[][] cloud , copyCloud;
// 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙
static int [] dr = {0,0,-1,-1,-1,0,1,1,1};
static int [] dc = {0,-1,-1,0,1,1,1,0,-1};
[1. 맨 처음으로 비바라기를 시전하여 (N,1) , (N-2) , (N-1,1),(N-1,2) 비 구름을 만든다. ]
public static void makeFirstCloud(int n){
cloud[n-1][0] = true;
cloud[n-1][1] = true;
cloud[n-2][0] = true;
cloud[n-2][1] = true;
}
[2. 구름을 이동시키고 , 이동 시킨 위치에 +1]
모든 구름을 d방향으로 s칸 이동시켜주어야한다.
s번 반복하여 d 방향으로 한번씩 이동시켜도 되지만, s번 만큼 이동하였을 때의 구름의 좌표를 한번에 구해보려고 한다.
예를 들어 길이가 5인 1차원배열이 있다. -> 인덱스 0 1 2 3 4
왼쪽으로 구름을 이동시키고 싶다면 현재 구름이 있는 좌표에 -1을 해주면된다.
현재 구름의 좌표가 2였을때 현재좌표 + ( -1 + 배열크기 5) % 배열크기 5 = (2+4) % 5 = 1 이 나와 2의 왼쪽좌표 값이 나오게 된다.
왼쪽으로 3번 이동 시키고 싶다면? (2+ (-1 + 배열크기 5)*이동회수 3) % 배열크기 5 = 4 이며 경계를 넘어서 좌표값을 구할 수 있게된다.
따라서 (현재좌표 + ( 이동방향 값 + 배열크기) * 이동 회수 ) % 배열크기 를 해주면 d 방향으로 s번 만큼 이동한 구름의 좌표를 구할 수 있다.
public static void moveCloud(int d ,int s){
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if(cloud[r][c]){
//d방향으로s번 이동한 구름 좌표 =(현재좌표 + ( 이동방향 값 + 배열크기) * 이동 회수 ) % 배열크기
int nr = (r+ (dr[d] + N) * s) % N;
int nc = (c + (dc[d] + N) * s) % N;
map[nr][nc]++; //+1
copyCloud[nr][nc]=true; //이동한 구름의 위치
cloud[r][c]=false; // 구름을 이동시켰기 때문에 그 자리의 구름을 없앤다.
}
}
}
}
[3. 물복사 버그 마법 - 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니 수 만큼 바구니의 물 양을 증가시키기]
//경계를 넘어갔는지 체크
public static boolean inWall(int r , int c){
if(r >=N || c>=N || r<0 || c<0) return false;
return true;
}
//물복사버그 마법
public static void countDiagonal(){
for(int r =0 ; r<N; r++){
for(int c= 0; c<N;c++){
if(copyCloud[r][c]){ //구름이 사라진 위치일경우
for(int j=2 ; j<=8; j+=2){//↖,↗,↘, ↙
int nr =r+dr[j];
int nc= c+dc[j];
//경계를 넘어가지 않고 대각선 바구니에 물이 있는경우만 수를 세어준다.
if(inWall(nr,nc) && map[nr][nc]!=0){
map[r][c]++;
}
}
}
}
}
}
[4. 구름이 사라진 위치를 제외하고 바구니에 저장된 물의 양이 2이상인 모든 칸에 구름이 생기고 , 물의 양은 2 줄인다.]
public static void minusTwo(){
for(int r =0 ; r<N; r++){
for(int c= 0; c<N;c++){
//사라진 구름의 위치가 아니고 물의 양이 2이상일 경우
if(!copyCloud[r][c] && map[r][c]>=2){
map[r][c]-=2;
cloud[r][c]=true; //구름생김
}
//사라진 구름의 위치를 지워준다.
else if(copyCloud[r][c]) copyCloud[r][c]=false;
}
}
}
[코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//마법사 상어와 비바라기
public class Main {
static int N,M;
static int[][] map ;
static boolean[][] cloud , copyCloud;
// 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙
static int [] dr = {0,0,-1,-1,-1,0,1,1,1};
static int [] dc = {0,-1,-1,0,1,1,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()," ");
N=Integer.parseInt(st.nextToken());
M= Integer.parseInt(st.nextToken());
map = new int[N][N];
cloud = new boolean[N][N];
copyCloud = new boolean[N][N];
for(int i = 0; i <N;i++){
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j <N; j++){
map[i][j]=Integer.parseInt(st.nextToken());
}
}
//처음 구름 만들기
makeFirstCloud(N);
for(int i = 0 ; i <M; i++){
st = new StringTokenizer(br.readLine(), " ");
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
//구름이동 , +1
moveCloud(d,s);
//대각선 체크
countDiagonal();
//2만큼 빼기
minusTwo();
}
//총합
System.out.println(total());
}
public static void makeFirstCloud(int n){
cloud[n-1][0] = true;
cloud[n-1][1] = true;
cloud[n-2][0] = true;
cloud[n-2][1] = true;
}
public static void moveCloud(int d ,int s){
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if(cloud[r][c]){
int nr = (r+ (dr[d] + N) * s) % N;
int nc = (c + (dc[d] + N) * s) % N;
map[nr][nc]++;
copyCloud[nr][nc]=true;
cloud[r][c]=false;
}
}
}
}
public static boolean inWall(int r , int c){
if(r >=N || c>=N || r<0 || c<0) return false;
return true;
}
public static void countDiagonal(){
for(int r =0 ; r<N; r++){
for(int c= 0; c<N;c++){
if(copyCloud[r][c]){
for(int j=2 ; j<=8; j+=2){
int nr =r+dr[j];
int nc= c+dc[j];
if(inWall(nr,nc) && map[nr][nc]!=0){
map[r][c]++;
}
}
}
}
}
}
public static void minusTwo(){
for(int r =0 ; r<N; r++){
for(int c= 0; c<N;c++){
if(!copyCloud[r][c] && map[r][c]>=2){
map[r][c]-=2;
cloud[r][c]=true;
}
else if(copyCloud[r][c]) copyCloud[r][c]=false;
}
}
}
public static int total(){
int answer=0;
for(int r =0; r <N;r++){
for(int c =0; c<N;c++){
answer+=map[r][c];
}
}
return answer;
}
}[결과]
'Baekjoon' 카테고리의 다른 글
| [Java] 백준 1043 : 거짓말 (0) | 2022.10.01 |
|---|---|
| [Java] 백준 10159 : 저울 (0) | 2022.04.14 |
| [Java] 백준 18111번 : 마인크래프트 (0) | 2022.01.16 |
| [Java] 백준 1929번 : 소수 구하기 (0) | 2022.01.16 |
| [Java] 백준 2751번 : 수 정렬하기 2 (0) | 2022.01.15 |
