Baekjoon 8972 미친 아두이노 JAVA

8972번: 미친 아두이노

문제

요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해 다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.

게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.

1. 먼저, 종수가 아두이노를 8가지 방향(수직, 수평, 대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
2. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
3. 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1, s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
4. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
5. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게 된 경우에는 몇 번째 움직임에서 죽는지를 구한다.

조건

[입력]

첫째 줄에 보드의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.

마지막 줄에는 길이가 100을 넘지 않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

보드를 벗어나는 입력은 주어지지 않는다.

 

[출력]

중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

풀이

해당 문제는 시뮬레이션 문제로 문제에서 주어진 대로 구현을 진행하면 해결 가능한 문제다. 로직은 아래와 같은 방식으로 구현하였다.

다만 R을 이동시킬 때 R 간에 충돌을 체크하기 위해 새로운 배열에 이동시켜줌으로써 이동 전의 R과 이동 후의 R 충돌을 방지할 수 있었다.

 

1. 입력 처리를 한다 이때 I는 좌표값을 저장하고, R은 큐에 좌표값을 담아준다.

2. 무한 반복을 돌면서 아래와 같은 로직을 수행한다.

3. I를 이동시킨다.

    3-1. 이동 방향에 대해 좌표값을 경신해주고 이동하려는 곳이 R인 경우 종료한다.

4. R을 이동시킨다.

    4-1. 큐에 크기만큼 반복하며 큐에서 빼낸 좌표와 I 좌표를 비교한다.

    4-2. 비교를 통해 좌표 선상의 위치를 체크하여 연산을 한다. (같은 가로 선상, 같은 세로 선상, 대각선 이동)

    4-3. 이동하려는 곳이 I좌표와 같다면 종료한다.

    4-4. 큐에 이동하려는 좌표를 담는다.

5.  R을 모두 이동시키면 map를 갱신한다.

    5-1. 새로운 배열을 하나 생성한다 (R끼리 만나는 부분을 체크하기 위해, 기존 R과 충돌을 방지하기 위해)

    5-2. 큐가 빌 때까지 모두 빼내어 새로운 배열을 갱신한다 (이때 이미 R인 경우 X로 변경시킴)

    5-3. 갱신이 완료되면 배열을 탐색하면서 R인 부분은 큐에 담고 이외 부분은.으로 초기화한다.

    5-4. 새로운 배열 값을 map로 복사한다.

6. 카운트를 1 증가시키고 이동방향을 담은 배열의 크기와 비교한다.

    6-1. 사이즈가 같으면 map 배열을 출력하고 종료한다.

    6-2. 사이즈가 다르면 위의 동작을 반복한다.

코드

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

public class Main {
	
	static int R, C, ay, ax, cnt, dy[] = {0,1,1,1,0,0,0,-1,-1,-1}, dx[] = {0,-1,0,1,-1,0,1,-1,0,1}; // 1~9지니깐 첫번째에 더미 추가
	static char map[][], index[];
	static Queue<Node> q = new LinkedList<>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		for (int i = 0; i < R; i++) { // 입력처리
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				if(map[i][j] == 'I') {
					map[i][j] ='.';
					ay = i;
					ax = j;
				}else if(map[i][j] == 'R') {
					q.add(new Node(i,j));
				}
			}
		}
		index = br.readLine().toCharArray(); // 이동해야하는 방향 저장
		
		while(true) {
			if(move_Arduino()) { // 아두이노를 이동시킨다.
				System.out.println("kraj "+(cnt+1));
				break;
			}
			if(move_Crazy_Arduino()) { // 미친 아두이노를 이동시킨다.
				System.out.println("kraj "+(cnt+1));
				break;
			}
			map_Check();
			if(++cnt == index.length) { // 모두 이동했다면 출력하고 종료
				print();
				break;
			}
		}
	}
	
	private static void print() {
		map[ay][ax] = 'I';
		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 map_Check() { // 이동시킨 좌표를 가지고 map를 갱신함 이때 새로운 배열을 만들어서 큐에있는 값을 갱신해줌 R에대해서 기존값과 충돌 방지
		char copy[][] = new char[R][C];
		while(!q.isEmpty()) {
			Node n = q.poll();
			if(copy[n.y][n.x] != 'R' && copy[n.y][n.x] != 'X') // R의 단순 이동
				copy[n.y][n.x] = 'R';
			else // R이 있는곳으로 이동
				copy[n.y][n.x] = 'X';
		}
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(copy[i][j] == 'R') // R은 큐에 다시 담고
					q.add(new Node(i,j));
				else // null 과 X 는 .으로 갱신
					copy[i][j] = '.';
				map[i][j] = copy[i][j]; // 배열 복사
			}		
		}

	}

	private static boolean move_Crazy_Arduino() { // 큐의 사이즈만큼 돌면서 이동시키고 다시 큐에담음
		int size = q.size();
		for(int i= 0;i<size;i++) { 
			Node n = q.poll();
			if(n.y == ay) { // 같은 가로 선상
				if(n.x > ax)
					n.x--;
				else
					n.x++;
			}else if(n.x == ax) { // 같은 세로 선상
				if(n.y > ay)
					n.y--;
				else
					n.y++;
			}else { // 대각선 이동
				// 여기는 사분면으로 총 4가지 조건으로 체크
				if (ay > n.y  && ax > n.x) { // 오른쪽 상단으로 이동
					n.y++;
					n.x++;
				}else if (ay < n.y  && ax > n.x) { // 오른쪽 하단으로 이동
					n.y--;
					n.x++;
				}else if (ay < n.y  && ax < n.x) { // 왼쪽 상단으로 이동
					n.y--;
					n.x--;
				}else if (ay > n.y  && ax < n.x) { // 왼쪽 하단으로 이동
					n.y++;
					n.x--;
				}
			}
			if(n.y == ay && n.x == ax) // 이동한곳이 I 좌표라면 종료
				return true;
			q.add(new Node(n.y,n.x));
		}
		return false;
	}

	private static boolean move_Arduino() { // 이동방향 값을 더해주고 R인 경우 실패
		ay += dy[index[cnt] - '0'];
		ax += dx[index[cnt] - '0'];
		if(map[ay][ax] == 'R') {
			return true;
		}
		return false;
	}

	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드