[백준/boj] 8972: 미친 아두이노 / 구현 / 시뮬레이션

문제

8972번: 미친 아두이노

풀이

전체 코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int R, C;
	static char[][] map;
	static int[][] visited;
	static Pos jongsu;
	static Deque<Pos> crazyAdu = new ArrayDeque<Pos>();
	static int[] dx = { 0, 1, 1, 1, 0, 0, 0, -1, -1, -1 };
	static int[] dy = { 0, -1, 0, 1, -1, 0, 1, -1, 0, 1 };
	static Deque<Integer> jongsuDirs = new ArrayDeque<Integer>();
	static int cnt = 0;

	private static class Pos {
		int x;
		int y;

		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		visited = new int[R][C];
		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] == 'R')
					crazyAdu.add(new Pos(i, j));
				else if (map[i][j] == 'I')
					jongsu = new Pos(i, j);
			}
		}

		char[] chars = br.readLine().toCharArray();
		for (char c : chars) {
			jongsuDirs.add(c - '0');
		}

		while (!jongsuDirs.isEmpty()) {
			if (moveJongsu(jongsu.x, jongsu.y)) {
				if (!moveCrazyAduino()) {
					System.out.println("kraj " + cnt);
					return;
				}
				popAdu();
			} else {
				// 중간에 진경우 return !!
				System.out.println("kraj " + cnt);
				return;
			}
		}
		for(int i=0; i< R; i++) {
			for (int j=0; j<C; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}

	private static void popAdu() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (visited[i][j] > 1) {
					map[i][j] = '.';
				} else if(visited[i][j] ==1) {
					crazyAdu.add(new Pos(i, j));
				}
				visited[i][j] = 0;
			}
		}
	}

	private static boolean moveCrazyAduino() { // false: 종수랑 만남
		int nx, ny;
		int minNum = Integer.MAX_VALUE;
		int minX, minY;
		Deque<Pos> pos = new ArrayDeque<Pos>();
		while(!crazyAdu.isEmpty()) {
			minNum = Integer.MAX_VALUE;
			Pos aduDir = crazyAdu.pollFirst();
			minX = aduDir.x;
			minY = aduDir.y;
			for (int d = 1; d <= 9; d++) {
				nx = aduDir.x + dx[d];
				ny = aduDir.y + dy[d];
				if (isRange(nx, ny)) {
					int dir = calcDir(jongsu.x, jongsu.y, nx, ny);
					if (dir < minNum) {
						minNum = dir;
						minX = nx;
						minY = ny;
					}
				}
			}
			map[aduDir.x][aduDir.y] = '.';
			if (map[minX][minY] == 'I') {
				return false;
			}
			pos.add(new Pos(minX, minY));
			visited[minX][minY]++;
		}
		while(!pos.isEmpty()) {
			Pos p = pos.poll();
			map[p.x][p.y] = 'R';
		}
		return true;
	}

	private static boolean moveJongsu(int x, int y) {
		cnt++;
		int dir = jongsuDirs.pollFirst();
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (map[nx][ny] == 'R')
			return false;
		map[x][y] = '.';
		map[nx][ny] = 'I';
		jongsu.x = nx;
		jongsu.y = ny;
		return true;
	}

	static boolean isRange(int x, int y) {
		return x < 0 || x >= R || y < 0 || y >= C ? false : true;
	}

	static int calcDir(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}
}

클래스 설명

Pos(int x, int y) : x좌표와 y좌표를 담는 클래스

변수 설명

• jongsu (Pos) : 종수의 위치를 나타낸다.
• map (char[][]) : 현재 보드 상태
• visited (int[][]) : 로봇이 이동한 곳의 숫자를 증가시킨다. (2이상이면 폭파하기 위해)
• crazyAdu (Deque<Pos>) : 미친 아두이노들의 위치를 담아놓는다.
• dx, dy (int[]) : 이동하는 위치를 나타낸다. 0~ 9 까지 있다.
• jongsuDirs (Deque<Integer>) : 입력의 마지막 줄을 받아놓는다. 한판에 하나씩 빼서 모두 빠지면 이동이 끝난 것이므로 게임이 끝난 게 된다.
• cnt (int) : 종수가 이동한 숫자를 나타낸다. 

함수 설명

• moveJongsu(x , y) : 종수를 이동시키는 함수 

	private static boolean moveJongsu(int x, int y) {
		cnt++;
		int dir = jongsuDirs.pollFirst();
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (map[nx][ny] == 'R')
			return false;
		map[x][y] = '.';
		map[nx][ny] = 'I';
		jongsu.x = nx;
		jongsu.y = ny;
		return true;
	}

1. 종수 이동 횟수를 증가 시킨다.
2. 종수 위치 정보를 담은 jongsuDirs에서 poll
3. 새로운 위치 좌표인 nx, ny 를 할당한다.
4. map[nx][ny] 가 'R' 이라는 것은 미친 아두이노를 만난 것이므로 false 반환
   • false가 반환되면 kraj cnt 가 출력된다.
5. 'R'이 아니면 먼저 기존 위치를 '.' 로 바꾼 후, 새로운 위치에 'I' 할당 (여기서 이 둘의 순서가 바뀌면 안된다. 만약 dir이 5여서 제자리인 경우엔 nx , ny 가 x, y 와 같으므로 I 다음 . 를 하면 지워지기 때문이다.)
6. 종수의 현재위치인 jongsu 를 nx, ny 로 바꿔준다.
7. 미친 아두이노를 만나지 않았으므로 true 반환 

• moveCrazyAduino() : 미친 아두이노들을 이동시킨다.

private static boolean moveCrazyAduino() { // false: 종수랑 만남
		int nx, ny;
		int minNum = Integer.MAX_VALUE;
		int minX, minY;
		Deque<Pos> pos = new ArrayDeque<Pos>();
		while(!crazyAdu.isEmpty()) {
			minNum = Integer.MAX_VALUE;
			Pos aduDir = crazyAdu.pollFirst();
			minX = aduDir.x;
			minY = aduDir.y;
			for (int d = 1; d <= 9; d++) {
				nx = aduDir.x + dx[d];
				ny = aduDir.y + dy[d];
				if (isRange(nx, ny)) {
					int dir = calcDir(jongsu.x, jongsu.y, nx, ny);
					if (dir < minNum) {
						minNum = dir;
						minX = nx;
						minY = ny;
					}
				}
			}
			map[aduDir.x][aduDir.y] = '.';
			if (map[minX][minY] == 'I') {
				return false;
			}
			pos.add(new Pos(minX, minY));
			visited[minX][minY]++;
		}
		while(!pos.isEmpty()) {
			Pos p = pos.poll();
			map[p.x][p.y] = 'R';
		}
		return true;
	}

1. 모든 아두이노를 이동시켜야하기 때문에 crazyAdu가 빌때까지 실행한다.
2. 종수와 가장 가까워지는 위치로 이동해야한다. minNum을 최대값으로 갱신한다.
3. 한 아두이노의 위치를 poll
4. minX, minY 는 9개의 좌표를 모두 비교해서 종수와 가장 가까워지는 좌표이다.
5. for 문 안에서 모든 주변을 calcDir을 통해 종수와의 거리를 계산한다.
6. 이전 위치는 . 으로 바꾼다.
7. 만약 map[minX][minY] 가 'I' 라는 것은 종수의 아두이노가 미친 아두이노를 만난 것이므로 false를 리턴한다.
   • false가 반환되면 kraj cnt가 출력된다.
8. pos Deque에 minX와 minY 를 add
   • 이때 바로 map[minX][minY]를 'R'로 바꾸면 만약 다음 미친 아두이노의 이전 위치가 map[minX][minY]와 같은 위치일 때  . 로 바뀌기 때문이다.
9. 모든 미친 아두이노의 가장 가까워지는 좌표가 결정되고 맵의 R 부분이 . 로 바뀌었을 때 pos Deque가 빌때까지 그 좌표 값들을 'R'로 바꿔준다. 
10. 종수를 안만났으면 게임이 안끝났으므로 true 반환

• popAdu() : 같은 칸에 있는 미친 아두이노 폭파시키기, visited 초기화, 미친 아두이노 위치 담는 함수

	private static void popAdu() { 
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (visited[i][j] > 1) {
					map[i][j] = '.';
				} else if(visited[i][j] ==1) {
					crazyAdu.add(new Pos(i, j));
				}
				visited[i][j] = 0;
			}
		}
	}

• visited를 탐색하면서 숫자가 2 이상이면 미친 아두이노가 겹쳐있는 것이므로 map을 '.' 로 바꾼다( 폭파)
• 2이상이 아니고 1이면 이는 미친 아두이노가 하나 존재한다는 것이므로 crazyAdu에 좌표값을 담는다. 
• visited는 한게임마다 초기화되어야 하기 때문에 visited[i][j] = 0 을 통해 초기화한다.