백준 20057 JAVA : 마법사 상어와 토네이도

문제

https://www.acmicpc.net/problem/20057

20057번: 마법사 상어와 토네이도

 

풀이 예상

시뮬레이션 문제

 

 

풀이방법 (접근 방법 & 시간복잡도)

먼저 이동 부분은 왼, 아, 오, 위 순으로

왼 아 오오 위위 왼왼왼 아아아 오오오오 위위위위 왼왼왼왼왼 ... 이런 방식으로 진행 되기 때문에

왼쪽과 오른쪽일때 한번씩 더 간다는 점을 이용했다.

int direction = 0; //왼아오위
int keep = 0;
//토네이도 순서 왼, 아, 오, 위 인데 왼,오 갈때는 횟수+1 해서 이동
while(true) {
	if(direction==0 || direction == 2) {
		keep++;
	}

	for (int i = 0; i < keep; i++) {
		move(direction); //움직이는 함수
	}
	direction++;
	direction%=4;
}

 

 

그리고 이동해서 모래를 분배하는 방법은

왼쪽이나 오른쪽 으로 이동하는 방향이면  x, y, a를 기준으로 위아래로 대칭이고, 

아래쪽이나 위쪽으로 이동하는 방향이면 x, y, a를 기준으로 양옆으로 대칭이 이루어져 있다.

 

이런 특징을 활용해서 분배하는 함수를 작성하면 이런식으로 나타낼 수 있다.

    static void divide(int dir, int r, int c, int mul, int num) { //이동방향, 이동전좌표(r,c), 몇번 이동하는지, 모래 수
        for (int d = 0; d < 4; d++) {
            if((dir + d)%2 == 0) continue;
            int r1 = r + dr[d] * mul;
            int c1 = c + dc[d] * mul;
            if(!check(r1,c1)) { //범위 밖이면 결과값에 추가
                result += num;
            }else { //범위 안이면 보드에 추가
                board[r1][c1] += num;
            }
            give += num; //준 값들 더하기

        }
    }

 

위의 방법들을 종합해서 코드를 작성하면 아래와 같다.

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N,r,c,result,give;
    static int[][] board;
    static int[] dr = {0, 1, 0, -1};//왼아오위 순
    static int[] dc = {-1, 0, 1, 0};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        board = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        r = N/2;
        c = N/2;
        int direction = 0; //왼아오위
        int keep = 0;
        //토네이도 순서 왼, 아, 오, 위 인데 왼,오 갈때는 횟수+1 해서 이동
        while(true) {
            if(direction==0 || direction == 2) {
                keep++;
            }

            for (int i = 0; i < keep; i++) {
                move(direction);
                if(r == 0 && c == 0) {
                    break;
                }
            }

            direction++;
            direction%=4;

            if(r == 0 && c == 0) {
                break;
            }

        }
        System.out.println(result);


    }
    static void move(int dir) {
        int nr = r + dr[dir];
        int nc = c + dc[dir];
        if(check(nr,nc) && board[nr][nc] != 0) {
            //나눠주기
            int init = board[nr][nc];
            give = 0;


            //r, c관점으로 왼,오 이동일 때는 위아래 한칸씩, 위아래이동일떄는 왼오한칸씩
            divide(dir, r,c,1,init/100);

            //nr, nc관점으로 왼오이동일때는 위아래 두칸씩, 위아래이동일때는 왼오두칸씩
            divide(dir, nr,nc,1,init*7/100);
            divide(dir, nr,nc,2,init*2/100);

            //nr+1, nc+1관점으로 왼오이동일때는 위아래 한칸씩, 위아래이동일떄는 왼오한칸씩
            divide(dir, nr+dr[dir],nc+dc[dir],1,init/10);

            //nr+2, nc+2에 5퍼센트
            if(!check(nr+2*dr[dir], nc+2*dc[dir])) {
                result += init * 5/100;
            }else {
                board[nr+2*dr[dir]][nc+2*dc[dir]] += init * 5/100;
            }
            give += init * 5/100;


            //남은거 a에 저장
            if(!check(nr+dr[dir],nc+dc[dir])) {
                result += (init - give);
            }else {
                board[nr+dr[dir]][nc+dc[dir]] += (init - give);
            }

        }

        r += dr[dir];
        c += dc[dir];
        board[r][c] = 0;

    }
    static boolean check(int nr, int nc) {
        return nr>=0 && nr<N && nc>=0 && nc<N;
    }
    static void divide(int dir, int r, int c, int mul, int num) {
        for (int d = 0; d < 4; d++) {
            if((dir + d)%2 == 0) continue;
            int r1 = r + dr[d] * mul;
            int c1 = c + dc[d] * mul;
            if(!check(r1,c1)) {
                result += num;
            }else {
                board[r1][c1] += num;
            }
            give += num;

        }
    }
}

 

결과