백준 8972 <미친 아두이노>

일반적인 시뮬레이션이다. 이러한 문제는 삼성에 나올법한 유형은 문제이기 때문에 풀어보길 추천한다.

 

문제 풀이

1. 종수의 아두이노를 움직인다.
2. 미친 아두이노와 만나면 return
3. 미친 아두이노가 담긴 queue를 이용해 8방향으로 움직여보고 가장 짧은 거리로 이동
4. 새로운 맵에 체크를 한다. 만약 종수 아두이노와 만났다 return
5.  미친 아두이노의 위치에 왔다 그 자리를 B--> 터짐 표시를 한다.
6. 새로운 맵을 기존 맵에 옮기면서 미친 아두이노가 터지지 않았다면 queue에 담아준다.

이 그림 처럼 계속 진행해주면 풀리는 문제이다.

 

 

미친 아두이노를 queue에서 꺼내서 이동해준다.

미친 아두이노의 다음 위치를 체크해주는 과정

생존한 미친 아두이노를 큐에 다시 넣어준다.

 

이 과정을 반복하면 해결할 수 있는 문제이다.

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {


	static int n, m,sx,sy,result,go[];
	static String map[][];
	static int dir[][]= {{0,0},{1,-1},{1,0},{1,1},{0,-1},{0,0},{0,1},{-1,-1},{-1,0},{-1,1}};
	static Queue<Point> q;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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 String[n][m];
		q=new LinkedList<Point>();
		for(int i=0;i<n;i++) {
			String s=br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j]="";
				map[i][j]+=s.charAt(j);
				if(map[i][j].equals("I")) {
					sx=i;
					sy=j;
				}
				else if(map[i][j].equals("R")) {
					q.add(new Point(i,j));
				}
			}
		}//초기화 완료
		String s=br.readLine();
		go=new int[s.length()];
		for(int i=0;i<go.length;i++) {
			go[i]=s.charAt(i)-'0';
		}
		simul();
		if(result==0) {
			StringBuilder sb=new StringBuilder();
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					sb.append(map[i][j]);
				}
				sb.append("\n");
			}
			System.out.println(sb);
		}
		else
			System.out.println("kraj " +result);
	}

	private static void simul() {
		// TODO Auto-generated method stub
		for(int i=0;i<go.length;i++) {
			String map2[][]=new String[n][m];
			sx+=dir[go[i]][0];
			sy+=dir[go[i]][1];
			//아두이노 이동
			if(map[sx][sy].equals("R")) {
				result=i+1;
				return;
			}//2번 아두이도를 밟음
			map2[sx][sy]="I";
			while(!q.isEmpty()) {
				Point next=q.remove();
				int d=Math.abs(sx-next.x)+Math.abs(sy-next.y);
				int movex=next.x;
				int movey=next.y;
				for(int j=1;j<=9;j++) {
					int x1=next.x+dir[j][0];
					int y1=next.y+dir[j][1];
					if(x1<0||x1>=n||y1<0||y1>=m) {
						continue;
					}
					int nextd=Math.abs(sx-x1)+Math.abs(sy-y1);
					if(nextd<d) {
						d=nextd;
						movex=x1;
						movey=y1;
					}
				}//8방향 이동 끝
				if(map2[movex][movey]!=null&&map2[movex][movey].equals("I")) {
					result=i+1;
					return;
				}
				else if(map2[movex][movey]!=null) {
					map2[movex][movey]="b";//터진것
				}
				else {
					map2[movex][movey]="R";
				}
			}
			for(int j=0;j<n;j++) {
				for(int k=0;k<m;k++) {
					if(map2[j][k]==null||map2[j][k].equals("b")) {
						map[j][k]=".";
					}
					else {
						map[j][k]=map2[j][k];
						if(map[j][k].equals("R"))
							q.add(new Point(j,k));
					}
				}
			}
		}
	}

	
}