[알고리즘] 시뮬레이션

시뮬레이션의 사전적 정의는 다음과 같다.

시뮬레이션 : 실제로 실행하기 어려운 과정을 간단히 행하는 모의실험

 

코딩테스트에서도 마찬가지로 간단하게 주어지는 조건을 따라 한단계씩 순차적으로 특정 과정을 수행하는 것을 말한다. 주로 캐릭터를 2차원 공간에서 이동하는 문제가 있다고 한다.

 

구현의 한 종류에 속하기 때문에 특정한 기술보다는 상세한 사고과정이 필요하다. 구현 문제는 머릿속으로 사고하기는 쉽지만 실제 코드로 옮기는 것이 어렵기 때문이다.

 

예시 문제로는 백준의 2638. 치즈가 있다.

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

 

적용한 문제 해결방식은 아래와 같다.

 

1. 치즈가 없어질 때까지 시간은 계속 흘러간다.

2. 한시간이 지난 뒤에 남은 치즈를 Flood Fill을 이용해 개수를 확인한다.

3. 치즈가 전부 사라졌을 때의 시간을 출력한다.

 

input:
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

output:
4


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] map;
	static int[][] visited;
	static int result;
	static Queue<int[]> que;
	
	public static void main(String[] args) throws Exception {
		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][M];
		
//		int one = 0;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
//				if(map[i][j]==1) one++;
			}
		}
		//입력---------
		//연산---------
		result = 0;
		while(true) {
			int one = 0;
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(map[i][j]==1) {
						one++; //치즈개수 카운트
					}
				}
			}
			if(one==0) break; //치즈가 없으면 중지
			visited = new int [N][M]; //방문배열초기화
			checkCheese(0,0); //bfs
			
//			for(int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(map[i]));
//			}
//			System.out.println();
			for(int i = 0; i < N; i ++) {
				for(int j = 0; j < M; j++) { //공기에 2번이상 닿은 치즈 삭제
					if(visited[i][j]>=2) map[i][j]=0;
				}
			}
			result++;

		}//while
		
		System.out.println(result);
	}

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	private static void checkCheese(int r, int c) {
		que = new LinkedList<>();
		que.offer(new int[] {r,c});
		
		while(!que.isEmpty()) {
			r = que.peek()[0];
			c = que.peek()[1];
			que.poll();
//			System.out.println(r+" "+c);
			
			for(int d = 0; d < 4; d++) { //사방탐색
				int nr = r+dr[d];
				int nc = c+dc[d];
				if(!check(nr,nc)) continue;
				if(visited[nr][nc]==-1) continue;
				if(map[nr][nc]==0) { //0이면 큐에 추가
					que.offer(new int[] {nr,nc});
					visited[nr][nc]=-1;
				}else { //1이면 방문배열에 체크
					visited[nr][nc]+=1;
				}
			}
		}
		
	}
	private static boolean check(int r, int c) {
		return r>=0 && r<N && c>=0 && c<M;
	}

}