백준 21610 - (Java, python) 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

 

1. 유형

시뮬레이션

 

2. 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, d, s;
	static int table[][];
	static ArrayList<int[]> clouds;
	static boolean visit[][];
	static int dir[][] = { { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 } };
	static int dir2[][] = { { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		init();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < N; j++) {
				table[i][j] = stoi(st.nextToken());
			}
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bf.readLine());
			d = stoi(st.nextToken()) - 1;
			s = stoi(st.nextToken());
			move(d, s);
			increase();
			decrease();
		}
		System.out.println(sum());
	}
	static int sum() {
		int answer = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				answer += table[i][j];
			}
		}
		return answer;
	}
	static void move(int d, int s) {
		for (int[] arr : clouds) {
			int nr = check(arr[0] + (dir[d][0] * s));
			int nc = check(arr[1] + (dir[d][1] * s));
			table[nr][nc] += 1;
			visit[nr][nc] = true;
		}
		clouds.clear();
	}

	static void increase() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(visit[i][j]) {
					for(int k=0; k<4; k++) {
						int nr = i+dir2[k][0];
						int nc = j+dir2[k][1];
						if(boundary(nr, nc) && table[nr][nc]>=1) {
							table[i][j]+=1;
						}
					}
				}
			}
		}
	}
	static void decrease() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visit[i][j] && table[i][j]>=2) {
					clouds.add(new int[] {i,j});
					table[i][j]-=2;
				}
			}
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				visit[i][j] = false;
			}
		}
	}
	static int check(int n) {
		while (n < 0) {
			n += N;
		}
		return n % N;
	}

	static void init() {
		table = new int[N][N];
		clouds = new ArrayList<>();
		visit = new boolean[N][N];
		clouds.add(new int[] { N - 1, 0 });
		clouds.add(new int[] { N - 1, 1 });
		clouds.add(new int[] { N - 2, 0 });
		clouds.add(new int[] { N - 2, 1 });
	}
	static boolean boundary(int r,int c) {
		if(r<0 || c<0 || r>=N || c>=N){
			return false;
		}
		return true;
	}
	private static int stoi(String nextToken) {
		// TODO Auto-generated method stub
		return Integer.valueOf(nextToken);
	}
}

 

import copy
def check(pos):
    res = pos
    if pos<0:
        res = (pos%N)
    elif pos>=N:
        res = (pos%N)
    return res

def move(cloud, d, s):
    ncloud = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if cloud[i][j]==1:
                nr = check(i+(dir[d][0])*s)
                nc = check(j+(dir[d][1])*s)
                ncloud[nr][nc] = 1
                table[nr][nc] += 1
    return ncloud
def increase(cloud):
    ntable = copy.deepcopy(table)
    for i in range(N):
        for j in range(N):
            if cloud[i][j]==1:
                cnt = 0
                for k in range(4):
                    nr = i+dir2[k][0]
                    nc = j+dir2[k][1]
                    if nr<0 or nc<0 or nr>=N or nc>=N:
                        continue
                    if table[nr][nc]>=1:
                        cnt+=1
                ntable[i][j]+=cnt
    return ntable

def decrease(cloud):
    ncloud = [[0 for _ in range(N)] for _ in range(N)]
    ntable = copy.deepcopy(table)
    for i in range(N):
        for j in range(N):
            if cloud[i][j] == 0 and table[i][j]>=2:
                ncloud[i][j] = 1
                ntable[i][j] -= 2
    return ncloud, ntable
def sum():
    ans = 0
    for lists in table:
        for el in lists:
            ans+=el
    return ans
if __name__=='__main__':
    N, M = map(int, input().split())
    table = [list(map(int, input().split())) for _ in range(N)]
    cloud = [[0 for _ in range(N)] for _ in range(N)]
    cloud[N-1][0], cloud[N-2][0], cloud[N-1][1], cloud[N-2][1] = 1, 1, 1, 1
    dir = [[0,-1], [-1,-1], [-1,0], [-1,1], [0,1],[1,1], [1,0], [1,-1]]
    dir2 = [[-1,-1], [-1,1], [1,1], [1,-1]]
    answer = 0
    for _ in range(M):
        d, s = map(int, input().split())
        cloud = move(cloud, d-1, s)
        table = increase(cloud)
        cloud, table = decrease(cloud)
    answer = sum()
    print(answer)

3. 자료구조

리스트

 

4. 풀이

 

모듈화가 중요한 문제

1) d방향으로 s칸씩 이동

2) 물 복사

3) 구름생성하고, 2씩 감소

4) 최종 합

 

 

이 문제에서 제일 까다로운 부분이 mod 연산인것 같다.

위와 같이 좌표가 범위를 넘어가도 다시 범위 안으로 들어오게 만들어야한다. 이때 mod 연산을 적용

음수인 경우 예외처리 해준다.

 

그 외에는 간단한 구현.