[백준, G3, 8972] 미친 아두이노

미친 아두이노 원본 및 입출력.zip

0.11MB

0. 문제 링크

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

8972번: 미친 아두이노

---

1. 문제 핵심

1. 아래 조건을 순서대로 진행하며 종료되는 조건에 맞게 결과를 출력해주면 된다.

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

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

---

2. 문제 접근

1. 처음에는 상태를 저장하는 2차원 배열 하나만 사용했는데 이러면 동시에 진행된다는 문제의 요건에 맞게 푸는 게 어려워질 수 있다.
   그래서 새로운 상태를 저장하는 2차원 배열을 하나 더 만들어주었고 한 턴이 모두 진행되었다면 그것을 본 배열에 다시 적용하였다.
2. 다만 문제 풀이 통과가 되지 않았는데 처리되지 않은 미친 아두이노를 처리할 때 이미 그 자리는 파괴되는 자리라고 파악하면 그 아두이노를 진행하지 않는 것이다. 이 문장을 제거하자 통과하였다.
3. 에러 케이스를 찾기 위해 문제 원본을 참고하였고 첨부하겠다.

---

3. 코드 분석

1.  

---

4. 베스트 코드 분석

1.  

---

5. 코드

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

class Main {
	static boolean isOut(int Y, int X, int N) {
		if (Y < 1 || Y > N || X < 1 || X > N)
			return true;
		return false;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());

		// 아두이노 위치 저장
		int[][] bd = new int[R][C];
		char[] tmpCharArr;
		// 지도 입력
		List<int[]> tmp = new LinkedList<>();
		int[] jong = new int[2];
		int nextNum = 2;
		for (int i = 0; i < R; i++) {
			tmpCharArr = br.readLine().toCharArray();

			for (int j = 0; j < C; j++) {
				// 종수
				if (tmpCharArr[j] == 'I') {
					jong[0] = i;
					jong[1] = j;
					bd[i][j] = 1;
				}
				// 미친 아두이노
				else if (tmpCharArr[j] == 'R') {
					bd[i][j] = nextNum;
					nextNum++;
					tmp.add(new int[] { i, j, 0 });
				}
			}
		}

		// y, x, 존재유무
		int[][] robots = new int[tmp.size() + 2][3];

		for (int i = 2; i < tmp.size() + 2; i++) {
			robots[i] = tmp.get(i - 2);
		}

		// 명령문 구분자
		String order = br.readLine();
		int[] orderList = new int[order.length()];
		for (int i = 0; i < order.length(); i++) {
			orderList[i] = order.charAt(i) - '0';
		}
		// 좌하 하 우하
		// 좌 중 우
		// 좌상 상 우상
		int[][] dydx = new int[][] { //
				{ 0, 0 }, //
				{ 1, -1 }, { 1, 0 }, { 1, 1 }, //
				{ 0, -1 }, { 0, 0 }, { 0, 1 }, //
				{ -1, -1 }, { -1, 0 }, { -1, 1 } };

		int jongNextY, jongNextX, rNY, rNX, another = 0;
		int[][] tmpBoard;
		Queue<int[]> xList = new LinkedList<>();
		int[] crntR;

		// 게임 실행
		int shortest, shortestDir = 0;
		for (int i = 0; i < orderList.length; i++) {
			// 1. 종수의 다음 위치
			jongNextY = jong[0] + dydx[orderList[i]][0];
			jongNextX = jong[1] + dydx[orderList[i]][1];

			// 2. 빈칸이 아니고 자기 자신이 아닌 경우
			if (bd[jongNextY][jongNextX] >= 2) {
				System.out.println("kraj " + (i + 1));
				return;
			}
			// 종수 위치 최신화
			jong[0] = jongNextY;
			jong[1] = jongNextX;
			tmpBoard = new int[R][C];

			tmpBoard[jong[0]][jong[1]] = 1;

			// 로봇 순회
			for (int j = 2; j < robots.length; j++) {
				// 이미 파괴된 경우
				if (robots[j][2] == 1)
					continue;

				// 초기화
				shortest = Integer.MAX_VALUE;
				// 로봇 구방 탐색
				for (int k = 1; k <= 9; k++) {
					if (k == 5)
						continue;
					rNY = robots[j][0] + dydx[k][0];
					rNX = robots[j][1] + dydx[k][1];

					// 가장 짧아지는 방향 탐색
					if (Math.abs(jong[0] - rNY) + Math.abs(jong[1] - rNX) < shortest) {
						shortest = Math.abs(jong[0] - rNY) + Math.abs(jong[1] - rNX);
						shortestDir = k;
					}
				}

				// 3. 로봇 위치 최신화
				robots[j][0] += dydx[shortestDir][0];
				robots[j][1] += dydx[shortestDir][1];

				// 4. 종수와 겹칠 때
				if (tmpBoard[robots[j][0]][robots[j][1]] == 1) {
					System.out.println("kraj " + (i + 1));
					return;
				}
				// 빈칸인 경우
				else if (tmpBoard[robots[j][0]][robots[j][1]] == 0) {
					tmpBoard[robots[j][0]][robots[j][1]] = j;
				}
				// 5. 다른 로봇들과 겹쳐서 파괴되는 자리인 경우
				else if (tmpBoard[robots[j][0]][robots[j][1]] == -1) {
					robots[j][2] = 1;
				}
				// 다른 아두이노와 겹치는 경우
				else {
					// 이전에 그 자리에 이동한 아두이노 번호
					another = tmpBoard[robots[j][0]][robots[j][1]];
					tmpBoard[robots[j][0]][robots[j][1]] = -1;// 해당 자리 터지는 표시
					// 두 로봇 사용 불가 처리
					xList.add(new int[] { robots[j][0], robots[j][1] });
					robots[another][2] = 1;
					robots[j][2] = 1;
				}
				System.out.print("");
			}

			while (!xList.isEmpty()) {
				crntR = xList.poll();
				tmpBoard[crntR[0]][crntR[1]] = 0;
			}

			// 보드 갱신
			for (int j = 0; j < R; j++)
				bd[j] = tmpBoard[j];
		}

		for (int l = 0; l < R; l++) {
			for (int l2 = 0; l2 < C; l2++) {
				// 종수
				if (bd[l][l2] == 1)
					System.out.print('I');
				// 빈칸
				else if (bd[l][l2] == 0)
					System.out.print('.');
				// 미친 아두이노
				else
					System.out.print('R');
			}
			System.out.println();
		}
	}
}

 

※ 미라콤아이앤씨 코테에 이와 비슷한 문제가 나왔는데 그 땐 풀지 못했다. 이번 문제에 도전하며 이러한 동시 진행 구현 문제에 대한 인사이트를 얻을 수 있었다.