[백준 - Java] 8972번 : 미친 아두이노

문제

www.acmicpc.net/problem/8972

8972번: 미친 아두이노

주절주절...

어떻게 하면 최적으로 문제를 풀 수 있을까 고민을 많이 했던 문제다.

미친 아두이노가 파괴되었나 안되었나 상태 변수를 만들어 관리하기도 했었고, 

반례를 생각하지 못한 코드를 짠 경우도 있었고 (ex. 2개 이상의 미친 아두이노가 같은 칸으로 이동하는 경우)

같은 칸으로 이동할 경우 이전에 이동한 아두이노를 미리 움직여서 보드판이 뒤죽박죽으로 나오기도 하고...

맵을 지웠다. 다시 썼다. 복사했다... 시간 초과도 나고 ㅠㅠ

근데 막상 머리를 비우고 풀고 나니 진짜 문제에서 하라는 대로 하면 됐음;;;

 

이제 내가 푼 문제에 대해 설명해보겠다! 

문제 조건

게임은 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는 종수가 게임이 끝나기 전까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

설명 

움직이려는 방향에 따라 종수와 미친 아두이노를 이동하면서 게임을 진행한다.

 

1. 먼저 내 아두이노가 이동한다.
2. 다음으로 미친 아두이노가 이동한다.
3. 이동된 값에 맞게 보드를 재구성한다.

위의 3 과정이 계속해서 반복되며,

게임의 완벽한 종료 조건은 모든 움직이는 횟수만큼 게임을 진행하고 마지막 보드를 출력하는 것이다.

 

하지만 1 과정에서 내 아두이노가 미친 아두이노를 만나거나,

2 과정에서 미친 아두이노가 내 아두이노를 만나면 게임이 중간에 종료된다. 

중간에 종료될 경우 kraj X로 게임이 끝나기 전까지 움직인 횟수를 출력한다.

 

입력받기 

스캐너를 통해 입력받고 char형의 이차원 배열에 보드를 구성해준다.

8방향 이동을 위해 dx, dy 좌표 배열을 만들었다.

 

내 아두이노의 위치를 myArduino 변수로 관리하고

미친 아두이노들은 LinkedList에 저장해 관리한다.

 

움직이려는 방향은 stream을 사용해 문자열을 자른 뒤 int형 배열에 넣어줬다.

 

static int R, C;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static char[][] board;
	static Point myArduino;
	static LinkedList<Point> crazyArduino = new LinkedList<>();
   
	// 1하좌, 2하, 3하우, 4좌, 5그대로, 6우, 7상좌, 8상, 9상우 
	static int[] dx = {1, 1, 1, 0, 0, 0, -1, -1, -1}; 
	static int[] dy = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();

		board = new char[R][C];

		for(int i = 0; i < R; i++) {
			String str = sc.next();
			for(int j = 0; j < C; j++) {
				board[i][j] = str.charAt(j);

				if(board[i][j] == 'I') { // 내 아두이노 
					myArduino = new Point(i, j);
				} else if(board[i][j] != '.') { // 미친 아두이노 
					Point p = new Point(i, j);
					crazyArduino.add(p);
				}
			}
		}
        
        int[] dir = Arrays.stream(sc.next().split("")) // 움직이려는 방향 
		.mapToInt(Integer::parseInt)
		.toArray();
	}
}

게임 시작 및 출력 코드 

kraj 변수를 만들어 게임이 중간에 끝날 경우 그때까지의 이동 횟수를 저장한다.

움직이려는 방향의 개수만큼 게임을 수행한다.

 

int kraj = 0; // 게임이 끝나기 전 까지 이동한 횟수

// 게임 시작 
for(int i = 0; i < dir.length; i++) {
	// 1. 내 아두이노 이동 
	if(dir[i] != 5) { // 그대로인 경우 제외 
		// false 반환 -> 이동한 곳에 미친 아두이노가 있음 -> 게임 종료 
		if(!moveMyArduino(dir[i]-1)) { 
			kraj = i+1;
			break;
		}
	}

	// 2. 미친 아두이노 이동
	if(!moveCrazyArduino()) { // false 반환 -> 이동한 곳에 내 아두이노가 있음 -> 게임 종료 
		kraj = i+1;
		break;
	}

	// 3. 보드 새로 구성하기 (이동된 값에 따라 새롭게 보드 구성)
	makeBoard();
}

if(kraj != 0) {
	System.out.println("kraj " + kraj); // 중간에 끝난 경우 
} else {
	print(); // 중간에 끝나지 않고 모두 이동한 경우 보드 출력 
}

1. 내 아두이노 이동

움직여야 할 방향으로 이동 후,

이동할 방향에 미친 아두이노가 있다면 false를 반환하며 게임 종료

빈칸이라면 새로운 좌표로 위치를 갱신한다.

 

// 1. 내 아두이노 이동 
public static boolean moveMyArduino(int dir) {
	int nx = myArduino.x + dx[dir];
	int ny = myArduino.y + dy[dir];

	if(board[nx][ny] == 'R') {
		return false;
	} else {
		myArduino.x = nx;
		myArduino.y = ny;
		return true;
	}
}

2. 미친 아두이노 이동

BFS를 수행하는 것과 비슷하게 수행한다.

 

미친 아두이노 리스트의 사이즈만큼 미친 아두이노들을 꺼내 보며 이동을 수행한다.

temp 배열을 만들어 2개 이상의 미친 아두이노가 같은 칸으로 이동했는지를 판별한다. 

 

1. 보드판 범위를 벗어나지 않는 선에서 8방향으로 이동시켜본다.

8방향을 이동하면서 내 아두이노와 가장 가까워지는 방향을 min 값으로 구한 뒤 그때의 x, y좌표값을 minX, minY에 저장한다.

 

2. 8방향 모두 이동하며 가장 가까워 지는 방향을 구한 뒤

해당 방향으로 1칸 이동할 위치에 내 아두이노가 있다면 false를 반환하고 게임을 종료한다.

 

3. 하지만 이동할 수 있다면  temp 배열의 이동할 위치에 해당하는 곳의 값을 +1 해준다.

 

모든 미친 아두이노들에 대해 8방향 이동을 통해 가장 가까워지는 방향으로 1칸 이동을 시켰다면,

temp 배열에 미친 아두이노들의 이동이 입력되었다.

 

temp배열을 순회하며 값이 1인 칸은 1개의 아두이노가 이동해서 왔다는 것을 의미한다.

따라서 이때의 좌표만 다시 미친 아두이노 LinkedList에 추가해 새롭게 미친 아두이노 리스트를 구성한다.

 

// 2. 미친 아두이노 이동 
public static boolean moveCrazyArduino() {
	int[][] temp = new int[R][C];

	int size = crazyArduino.size(); 
	for(int i = 0; i < size; i++) { // 미친 아두이노의 수만큼 반복 
		int x = crazyArduino.peek().x;
		int y = crazyArduino.poll().y;

		int min = Integer.MAX_VALUE; // 내 아두이노와 가장 가까워 지는 방향 구하기위한 변수 
		int minX = 0;
		int minY = 0;

		// 8방향 이동시켜 봄 
		for(int j = 0; j < 9; j++) {
			if(j == 4) continue; // 그대로인 경우 제외 

			int nx = x + dx[j];
			int ny = y + dy[j];

			if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 범위 벗어나면 제외 

			// 이동했을 때 가장 작아지는 방향 찾기 
			int val = Math.abs(myArduino.x - nx) + Math.abs(myArduino.y - ny);
			if(val < min) {
				min = val;
				minX = nx;
				minY = ny;
			}
		}

		if(minX == myArduino.x && minY == myArduino.y) { // 이동할 방향에 내 아두이노가 있는 경우 게임 종료 
			return false;
		} 

		temp[minX][minY] += 1; // 이동할 수 있다면 +1 
	}

	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) {
			if(temp[i][j] == 1) { // 칸에 1개의 아두이노만 있어야 파괴되지 않음 
				crazyArduino.add(new Point(i, j)); // 따라서 칸에 1개 있는 아두이노만 다시 미친 아두이노 리스트에 추가 
			}
		}
	}

	return true;
}

3. 보드 재구성

1, 2 과정을 수행 후, 내 아두이노, 미친 아두이노의 이동에 따라 새롭게 보드판을 구성해준다.

 

// 3. 보드 새로 구성하기 
public static void makeBoard() {
	board = new char[R][C];

	for(int i = 0; i < R; i++) // 빈칸 .으로 초기화 
		Arrays.fill(board[i], '.'); 

	board[myArduino.x][myArduino.y] = 'I'; // 내 아두이노 배치 

	for(int i = 0; i < crazyArduino.size(); i++) { // 미친 아두이노 배치 
		Point p = crazyArduino.poll();
		board[p.x][p.y] = 'R';
		crazyArduino.add(p);
	}
}

 

전체 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static int R, C;
	static char[][] board;
	// 1하좌, 2하, 3하우, 4좌, 5그대로, 6우, 7상좌, 8상, 9상우 
	static int[] dx = {1, 1, 1, 0, 0, 0, -1, -1, -1}; 
	static int[] dy = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
	static Point myArduino;
	static LinkedList<Point> crazyArduino = new LinkedList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();

		board = new char[R][C];

		for(int i = 0; i < R; i++) {
			String str = sc.next();
			for(int j = 0; j < C; j++) {
				board[i][j] = str.charAt(j);

				if(board[i][j] == 'I') { // 내 아두이노 
					myArduino = new Point(i, j);
				} else if(board[i][j] != '.') { // 미친 아두이노 
					Point p = new Point(i, j);
					crazyArduino.add(p);
				}
			}
		}

		int[] dir = Arrays.stream(sc.next().split("")) // 움직이려는 방향 
				.mapToInt(Integer::parseInt)
				.toArray();

		int kraj = 0; // 게임이 끝나기 전 까지 이동한 횟수

		// 게임 시작 
		for(int i = 0; i < dir.length; i++) {
			// 1. 내 아두이노 이동 
			if(dir[i] != 5) { // 그대로인 경우 제외 
				// false 반환 -> 이동한 곳에 미친 아두이노가 있음 -> 게임 종료 
				if(!moveMyArduino(dir[i]-1)) { 
					kraj = i+1;
					break;
				}
			}

			// 2. 미친 아두이노 이동
			// false 반환 -> 이동한 곳에 내 아두이노가 있음 -> 게임 종료 
			if(!moveCrazyArduino()) {
				kraj = i+1;
				break;
			}
			
			// 3. 보드 새로 구성하기 (이동된 값에 따라 새롭게 보드 구성)
			makeBoard();
		}

		if(kraj != 0) {
			System.out.println("kraj " + kraj); // 중간에 끝난 경우 
		} else {
			print(); // 중간에 끝나지 않고 모두 이동한 경우 보드 출력 
		}
	}

	// 1. 내 아두이노 이동 
	public static boolean moveMyArduino(int dir) {
		int nx = myArduino.x + dx[dir];
		int ny = myArduino.y + dy[dir];
		
		if(board[nx][ny] == 'R') {
			return false;
		} else {
			myArduino.x = nx;
			myArduino.y = ny;
			return true;
		}
	}

	// 2. 미친 아두이노 이동 
	public static boolean moveCrazyArduino() {
		int[][] temp = new int[R][C];

		int size = crazyArduino.size(); 
		for(int i = 0; i < size; i++) { // 미친 아두이노의 수만큼 반복 
			int x = crazyArduino.peek().x;
			int y = crazyArduino.poll().y;

			// 내 아두이노와 가장 가까워 지는 방향 구하기위한 변수 
			int min = Integer.MAX_VALUE; 
			int minX = 0;
			int minY = 0;

			// 8방향 이동시켜 봄 
			for(int j = 0; j < 9; j++) {
				if(j == 4) continue; // 그대로인 경우 제외 

				int nx = x + dx[j];
				int ny = y + dy[j];

				if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 범위 벗어남

				// 이동했을 때 가장 작아지는 방향 찾기 
				int val = Math.abs(myArduino.x - nx) + Math.abs(myArduino.y - ny);
				if(val < min) {
					min = val;
					minX = nx;
					minY = ny;
				}
			}

			// 이동할 방향에 내 아두이노가 있는 경우 게임 종료 
			if(minX == myArduino.x && minY == myArduino.y) { 
				return false;
			} 
			
			temp[minX][minY] += 1; // 이동할 수 있다면 +1 
		}

		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				if(temp[i][j] == 1) { // 칸에 1개의 아두이노만 있어야 파괴되지 않음 
					crazyArduino.add(new Point(i, j)); // 따라서 칸에 1개 있는 아두이노만 다시 미친 아두이노 리스트에 추가 
				}
			}
		}

		return true;
	}
	
	// 3. 보드 새로 구성하기 
	public static void makeBoard() {
		board = new char[R][C];
		
		for(int i = 0; i < R; i++) // 빈칸 .으로 초기화 
			Arrays.fill(board[i], '.'); 
		
		board[myArduino.x][myArduino.y] = 'I'; // 내 아두이노 배치 
		
		for(int i = 0; i < crazyArduino.size(); i++) { // 미친 아두이노 배치 
			Point p = crazyArduino.poll();
			board[p.x][p.y] = 'R';
			crazyArduino.add(p);
		}
	}

	// 보드판 출력 
	public static void print() {
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				System.out.print(board[i][j]);
			} System.out.println();
		}
	} 

}

class Point {
	int x;
	int y;

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

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%238972/src/Main.java

KwonMinha/BOJ