[Algorithm] ๐Ÿงน๋ฐฑ์ค€ 17144 ๋ฏธ์„ธ๋จผ์ง€ ์•ˆ๋…•!

HaJingJingยท2021๋…„ 7์›” 2์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
90/119

0. ๋ฌธ์ œ

๋ฏธ์„ธ๋จผ์ง€๋ฅผ ์ œ๊ฑฐํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋ฅผ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์„ฑ๋Šฅ์„ ํ…Œ์ŠคํŠธํ•˜๊ธฐ ์œ„ํ•ด ๊ตฌ์‚ฌ๊ณผ๋Š” ์ง‘์„ ํฌ๊ธฐ๊ฐ€ Rร—C์ธ ๊ฒฉ์žํŒ์œผ๋กœ ๋‚˜ํƒ€๋ƒˆ๊ณ , 1ร—1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆด๋‹ค. ๊ตฌ์‚ฌ๊ณผ๋Š” ๋›ฐ์–ด๋‚œ ์ฝ”๋”ฉ ์‹ค๋ ฅ์„ ์ด์šฉํ•ด ๊ฐ ์นธ (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ์‹ค์‹œ๊ฐ„์œผ๋กœ ๋ชจ๋‹ˆํ„ฐ๋งํ•˜๋Š” ์‹œ์Šคํ…œ์„ ๊ฐœ๋ฐœํ–ˆ๋‹ค. (r, c)๋Š” rํ–‰ c์—ด์„ ์˜๋ฏธํ•œ๋‹ค.
๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋Š” ํ•ญ์ƒ 1๋ฒˆ ์—ด์— ์„ค์น˜๋˜์–ด ์žˆ๊ณ , ํฌ๊ธฐ๋Š” ๋‘ ํ–‰์„ ์ฐจ์ง€ํ•œ๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์„ค์น˜๋˜์–ด ์žˆ์ง€ ์•Š์€ ์นธ์—๋Š” ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๊ณ , (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์€ Ar,c์ด๋‹ค.

1์ดˆ ๋™์•ˆ ์•„๋ž˜ ์ ํžŒ ์ผ์ด ์ˆœ์„œ๋Œ€๋กœ ์ผ์–ด๋‚œ๋‹ค.

1. ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ํ™•์‚ฐ๋œ๋‹ค. ํ™•์‚ฐ์€ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๋Š” ๋ชจ๋“  ์นธ์—์„œ ๋™์‹œ์— ์ผ์–ด๋‚œ๋‹ค.

  • (r, c)์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€๋Š” ์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ํ™•์‚ฐ๋œ๋‹ค.
    ์ธ์ ‘ํ•œ ๋ฐฉํ–ฅ์— ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์žˆ๊ฑฐ๋‚˜, ์นธ์ด ์—†์œผ๋ฉด ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ๋Š” ํ™•์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค.
  • ํ™•์‚ฐ๋˜๋Š” ์–‘์€ Ar,c/5์ด๊ณ  ์†Œ์ˆ˜์ ์€ ๋ฒ„๋ฆฐ๋‹ค.
  • (r, c)์— ๋‚จ์€ ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์€ Ar,c - (Ar,c/5)ร—(ํ™•์‚ฐ๋œ ๋ฐฉํ–ฅ์˜ ๊ฐœ์ˆ˜) ์ด๋‹ค.
  1. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์ž‘๋™ํ•œ๋‹ค.
  • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ๋Š” ๋ฐ”๋žŒ์ด ๋‚˜์˜จ๋‹ค.
  • ์œ„์ชฝ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ๋ฐ˜์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•˜๊ณ , ์•„๋ž˜์ชฝ ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•œ๋‹ค.
  • ๋ฐ”๋žŒ์ด ๋ถˆ๋ฉด ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ๋ฐ”๋žŒ์˜ ๋ฐฉํ–ฅ๋Œ€๋กœ ๋ชจ๋‘ ํ•œ ์นธ์”ฉ ์ด๋™ํ•œ๋‹ค.
  • ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ ๋ถ€๋Š” ๋ฐ”๋žŒ์€ ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์—†๋Š” ๋ฐ”๋žŒ์ด๊ณ , ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๋กœ ๋“ค์–ด๊ฐ„ ๋ฏธ์„ธ๋จผ์ง€๋Š” ๋ชจ๋‘ ์ •ํ™”๋œ๋‹ค.

    ๋‹ค์Œ์€ ํ™•์‚ฐ์˜ ์˜ˆ์‹œ์ด๋‹ค.

    ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์— ์นธ์ด ์—†๊ธฐ ๋•Œ๋ฌธ์—, ๋‘ ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ํ™•์‚ฐ์ด ์ผ์–ด๋‚ฌ๋‹ค.

    ์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ๋ชจ๋‘ ํ™•์‚ฐ์ด ์ผ์–ด๋‚œ๋‹ค.

    ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์žˆ๋Š” ์นธ์œผ๋กœ๋Š” ํ™•์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š๋Š”๋‹ค.

    ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ๋ฐ”๋žŒ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉํ–ฅ์œผ๋กœ ์ˆœํ™˜ํ•œ๋‹ค.

    ๋ฐฉ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, T์ดˆ๊ฐ€ ์ง€๋‚œ ํ›„ ๊ตฌ์‚ฌ๊ณผ์˜ ๋ฐฉ์— ๋‚จ์•„์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ๊ตฌํ•ด๋ณด์ž.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— R, C, T (6 โ‰ค R, C โ‰ค 50, 1 โ‰ค T โ‰ค 1,000) ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ R๊ฐœ์˜ ์ค„์— Ar,c (-1 โ‰ค Ar,c โ‰ค 1,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ๊ฐ€ ์„ค์น˜๋œ ๊ณณ์€ Ar,c๊ฐ€ -1์ด๊ณ , ๋‚˜๋จธ์ง€ ๊ฐ’์€ ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์ด๋‹ค. -1์€ 2๋ฒˆ ์œ„์•„๋ž˜๋กœ ๋ถ™์–ด์ ธ ์žˆ๊ณ , ๊ฐ€์žฅ ์œ— ํ–‰, ์•„๋žซ ํ–‰๊ณผ ๋‘ ์นธ์ด์ƒ ๋–จ์–ด์ ธ ์žˆ๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— T์ดˆ๊ฐ€ ์ง€๋‚œ ํ›„ ๊ตฌ์‚ฌ๊ณผ ๋ฐฉ์— ๋‚จ์•„์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€์˜ ์–‘์„ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์œ„์น˜๋ฅผ ๊ตฌํ•จ
๐Ÿ’ก ๋ฏธ์„ธ๋จผ์ง€ ์ฐพ๊ธฐ
๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์œ„์น˜์™€ ๋ฏธ์„ธ๋จผ์ง€๋ฅผ Node์— ์ €์žฅํ•˜๊ณ  ์ด๋ฅผ ํ์— ๋„ฃ์Œ
๐Ÿ’ก ํ™•์‚ฐ
ํ์— ๋„ฃ์€ ์œ„์น˜๋ฅผ ๊บผ๋‚ด์„œ 5๋กœ ๋‚˜๋ˆ„์–ด์ฃผ๊ณ  ์‚ฌ๋ฐฉ์œผ๋กœ ํ™•์‚ฐ์‹œํ‚ด
ํ™•์‚ฐ์‹œํ‚จ ์–‘๋งŒํผ ๋นผ์คŒ
๐Ÿ’ก ๊ณต๊ธฐ์ฒญ์ •
๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์œ„์น˜๋ฅผ ๊ตฌํ•ด ์œ„ ์•„๋ž˜๋กœ ๋‚˜๋ˆˆ ๋‹ค์Œ,
์œ„์—๋Š” ์‹œ๊ณ„๋ฐฉํ–ฅ, ์•„๋ž˜๋Š” ๋ฐ˜์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ๋ฐฐ์—ด์„ ์›€์ง์ž„
๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ ๋ฐ”๋กœ ๋‚˜์˜ค๋Š” ๊ณต๊ธฐ๋Š” ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์—†์Œ!!
๐Ÿ’ก ๋ฏธ์„ธ๋จผ์ง€ ์ฐพ๊ธฐ ~ ๊ณต๊ธฐ์ฒญ์ •๊นŒ์ง€๋ฅผ T๋งŒํผ ๋ฐ˜๋ณตํ•จ
๐Ÿ’ก ๋ฐฐ์—ด์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€๋ฅผ ๋ชจ๋‘ ๋”ํ•จ

2. ํ•ต์‹ฌ ํ’€์ด

  1. ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์œ„์น˜๋ฅผ ๊ตฌํ•จ
if(map[i][j] == -1 && cleaner == -1) {
	cleaner = i;
}
  1. ๋ฏธ์„ธ๋จผ์ง€ ์ฐพ๊ธฐ
    ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์œ„์น˜์™€ ๋ฏธ์„ธ๋จผ์ง€๋ฅผ Node์— ์ €์žฅํ•˜๊ณ  ์ด๋ฅผ ํ์— ๋„ฃ์Œ
q = new LinkedList<>();
			
for(int i=0; i<R; i++) {
	for(int j=0; j<C; j++) {
		if(map[i][j] != 0 && map[i][j] != -1) {
			q.add(new Node(i,j,map[i][j]));
		}
	}
}
  1. ํ™•์‚ฐ
    ํ์— ๋„ฃ์€ ์œ„์น˜๋ฅผ ๊บผ๋‚ด์„œ 5๋กœ ๋‚˜๋ˆ„์–ด์ฃผ๊ณ  ์‚ฌ๋ฐฉ์œผ๋กœ ํ™•์‚ฐ์‹œํ‚ด && ํ™•์‚ฐ์‹œํ‚จ ์–‘๋งŒํผ ๋นผ์คŒ
static void diffusion() {
	while(!q.isEmpty()) {
		Node cur = q.poll();
		int dust = cur.d/5;
		int count = 0;
			
		if(dust == 0) 
			continue;
			
		for(int i=0; i<4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
				
			if(nx < 0 || nx >= R || ny<0 || ny>=C || map[nx][ny] == -1)
				continue;
				
			count++;
			map[nx][ny] += dust;
		}
			
		map[cur.x][cur.y] -= dust*count;
	}
}
  1. ๊ณต๊ธฐ์ฒญ์ •
    ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์˜ ์œ„์น˜๋ฅผ ๊ตฌํ•ด ์œ„ ์•„๋ž˜๋กœ ๋‚˜๋ˆˆ ๋‹ค์Œ,
    ์œ„์—๋Š” ์‹œ๊ณ„๋ฐฉํ–ฅ, ์•„๋ž˜๋Š” ๋ฐ˜์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ๋ฐฐ์—ด์„ ์›€์ง์ž„
    ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ ๋ฐ”๋กœ ๋‚˜์˜ค๋Š” ๊ณต๊ธฐ๋Š” ๋ฏธ์„ธ๋จผ์ง€๊ฐ€ ์—†์Œ!!
static void wind(int cleaner) {
	int up = cleaner;
	int down = cleaner+1;
		
	for(int i=up-1; i>0; i--) {
		map[i][0] = map[i-1][0];
	}
		
	for(int i=0; i<C-1; i++) {
		map[0][i] = map[0][i+1]; 
	}
		
	for(int i=0; i<up; i++) {
		map[i][C-1] = map[i+1][C-1];
	}
		
	for(int i=C-1; i>1; i--) {
		map[up][i] = map[up][i-1]; 
	}
		
	map[up][1] = 0; 
		
	for(int i=down+1; i<R-1; i++) {
		map[i][0] = map[i+1][0];
	}
		
	for(int i=0; i<C-1; i++) {
		map[R-1][i] = map[R-1][i+1]; 
	}
		
	for(int i=R-1; i>down; i--) {
		map[i][C-1] = map[i-1][C-1];
	}
		
	for(int i=C-1; i>1; i--) {
		map[down][i] = map[down][i-1]; 
	}
		
	map[down][1] = 0;
}
  1. ๋ฏธ์„ธ๋จผ์ง€ ์ฐพ๊ธฐ ~ ๊ณต๊ธฐ์ฒญ์ •๊นŒ์ง€๋ฅผ T๋งŒํผ ๋ฐ˜๋ณตํ•จ
while(T-->0) {
	q = new LinkedList<>();
			
	for(int i=0; i<R; i++) {
		for(int j=0; j<C; j++) {
			if(map[i][j] != 0 && map[i][j] != -1) {
				q.add(new Node(i,j,map[i][j]));
			}
		}
	}
			
	diffusion();
	wind(cleaner);
}
  1. ๋ฐฐ์—ด์— ์žˆ๋Š” ๋ฏธ์„ธ๋จผ์ง€๋ฅผ ๋ชจ๋‘ ๋”ํ•จ
static int cal() {
	int sum = 0;
	for(int i=0; i<R; i++) {
		for(int j=0; j<C; j++) {
			if(map[i][j] != -1 && map[i][j] != 0)
				sum += map[i][j];
		}
	}
		
	return sum;
}

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
public class Imple_13 {
	static int[][] map;
	static Queue<Node> q;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	static int R, C, T;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		R = Integer.parseInt(s[0]);
		C = Integer.parseInt(s[1]);
		T = Integer.parseInt(s[2]);
		
		map = new int[R][C];
		int cleaner = -1;
		
		for(int i=0; i<R; i++) {
			s = br.readLine().split(" ");
			for(int j=0; j<C; j++) {
				map[i][j] = Integer.parseInt(s[j]);
				
				 if(map[i][j] == -1 && cleaner == -1) {
						cleaner = i;
				}
			}
		}
		
		while(T-->0) {
			q = new LinkedList<>();
			
			for(int i=0; i<R; i++) {
				for(int j=0; j<C; j++) {
					if(map[i][j] != 0 && map[i][j] != -1) {
						q.add(new Node(i,j,map[i][j]));
					}
				}
			}
			
			diffusion();
			wind(cleaner);
		}
		
		int sum = cal();
		System.out.println(sum);
	}
	
	static void diffusion() {
		while(!q.isEmpty()) {
			Node cur = q.poll();
			int dust = cur.d/5;
			int count = 0;
			
			if(dust == 0) 
				continue;
			
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				if(nx < 0 || nx >= R || ny<0 || ny>=C || map[nx][ny] == -1)
					continue;
				
				count++;
				map[nx][ny] += dust;
			}
			
			map[cur.x][cur.y] -= dust*count;
		}
	}
	
	static void wind(int cleaner) {
		int up = cleaner;
		int down = cleaner+1;
		
		for(int i=up-1; i>0; i--) {
			map[i][0] = map[i-1][0];
		}
		
		for(int i=0; i<C-1; i++) {
			map[0][i] = map[0][i+1]; 
		}
		
		for(int i=0; i<up; i++) {
			map[i][C-1] = map[i+1][C-1];
		}
		
		for(int i=C-1; i>1; i--) {
			map[up][i] = map[up][i-1]; 
		}
		
		map[up][1] = 0; // ๊ณต๊ธฐ์ฒญ์ •๊ธฐ์—์„œ ๋ฐ”๋กœ ๋‚˜์˜จ ์• 
		
		for(int i=down+1; i<R-1; i++) {
			map[i][0] = map[i+1][0];
		}
		
		for(int i=0; i<C-1; i++) {
			map[R-1][i] = map[R-1][i+1]; 
		}
		
		for(int i=R-1; i>down; i--) {
			map[i][C-1] = map[i-1][C-1];
		}
		
		for(int i=C-1; i>1; i--) {
			map[down][i] = map[down][i-1]; 
		}
		
		map[down][1] = 0;
	}
	
	static int cal() {
		int sum = 0;
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if(map[i][j] != -1 && map[i][j] != 0)
					sum += map[i][j];
			}
		}
		
		return sum;
	}
	static class Node{
		int x;
		int y;
		int d;
		Node(int x, int y, int d){
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€