[G3] 백준 8972번 미친 아두이노 C++ 구현, 시뮬레이션

리뷰

 

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

종수의 아두이노를 조종하며 미친 아두이노를 피할 수 있는지 여부와 최종 이동 후 정보를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n, m : 맵의 세로/가로 크기를 저장할 변수
• arr : 맵 정보를 저장할 2차원 캐릭터 배열
• ax, ay : 종수의 아두이노의 현재 좌표를 저장하기 위한 변수
• Pos : 미친 아두이노들의 좌표를 정의하기 위한 구조체
• dx, dy : 방향 배열

 

함수

1. get_dist

int get_dist(int tx, int ty) {
	return abs(tx - ax) + abs(ty - ay);
}

 

미친 아두이노의 이동 예상 위치와 종수의 아두이노 위치의 거리를 구하기 위한 함수

 

2. print

void print(int time) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << (i == ax && j == ay ? 'I' : arr[i][j]);
		}
		cout << "\n";
	}
	cout << "time: " << time << "\n";
}

 

현재 시간 기준 아두이노들의 위치를 확인하기 위한 디버깅 함수

 

 

문제풀이

1. n, m값을 입력 받고, Pos타입의 큐 q를 초기화한다.
2. n*m크기의 맵 정보를 입력 받고, 'R'일 경우 q에 push, 'I'일 경우 ax, ay를 초기화한다. 기본값은 '.'
3. 변수 op에 종수의 아두이노 조종 정보를 저장한다.
4. op를 순회하며 변수 idx에 현재 조종값의 인덱스를 저장한다.
5. ax, ay를 다음 위치로 이동시킨다. 만약 이동 위치에 미친 아두이노가 존재할 경우 사망 정보를 출력, 조기 종료한다.
6. Pos타입의 큐 temp를 초기화한다.
7. q가 빌때까지 while루프를 수행하며, 미친 아두이노를 종수와 가장 가까운 거리로 이동시킨 뒤 temp에 위치 정보를 push한다.
8. temp를 순회하며 미친 아두이노를 이동시키고, 종수의 아두이노와 만난 경우 사망 정보를 출력, 조기 종료한다.
9. 이동 위치가 빈 땅 '.'라면 'R'로 표기한다, 만약 빈 땅이 아닌경우 'B'로 표기한다.
10. n*m크기의 맵을 순회하며 값이 'R'라면 q에 좌표를 push하고, 'B'라면 빈 땅 '.'로 변경해준다.
11. 모든 쿼리를 수행할때까지 기저 조건에 도달하지 않았다면 arr[ax][ay]를 'I'로 변경해준다.
12. n*m크기의 맵 정보를 출력한다.

 

트러블 슈팅

1. 종수의 아두이노가 이동한 위치에 미친 아두이노가 있을 경우에 대한 기저 조건 설정을 해주지 않아 WA를 받았다.
2. 종수의 아두이노 이동 후 사망할 경우에 대한 로직을 추가하여 AC를 받았다.

 

참고 사항

1. 종수가 움직이려고 하는 방향 정보는 100회를 넘지 않는다.
2. 보드를 벗어나는 입력은 주어지지 않는다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

const int N = 100;
int n, m;
char arr[N][N];
int ax, ay;
struct Pos {
	int x, y;
};
int dx[] = { 0, 1, 1, 1, 0, 0, 0, -1, -1, -1 };
int dy[] = { 0, -1, 0, 1, -1, 0, 1, -1, 0, 1 };

int get_dist(int tx, int ty) {
	return abs(tx - ax) + abs(ty - ay);
}

void print(int time) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << (i == ax && j == ay ? 'I' : arr[i][j]);
		}
		cout << "\n";
	}
	cout << "time: " << time << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	queue<Pos> q;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c; cin >> c;
			arr[i][j] = '.';

			if (c == 'R') {
				arr[i][j] = 'R';
				q.push({ i, j });
			}
			else if (c == 'I') {
				ax = i, ay = j;
			}
		}
	}

	string op; cin >> op;
	for (int i = 0; i < op.size(); ++i) {
		int idx = op[i] - '0';

		ax += dx[idx];
		ay += dy[idx];
		if (arr[ax][ay] == 'R') {
			cout << "kraj " << i + 1;
			return 0;
		}

		queue<Pos> temp;
		while (!q.empty()) {
			auto [cx, cy] = q.front(); q.pop();
			arr[cx][cy] = '.';

			int dist = 9999;
			int nx = -1, ny = -1;
			for (int i = 1; i <= 9; ++i) {
				if (i == 5) continue;

				int tx = cx + dx[i], ty = cy + dy[i];
				int n_dist = get_dist(tx, ty);
				if (n_dist < dist) {
					dist = n_dist;
					nx = tx, ny = ty;
				}
			}
			temp.push({ nx, ny });
		}

		while (!temp.empty()) {
			auto [x, y] = temp.front(); temp.pop();
			if (x == ax && y == ay) {
				cout << "kraj " << i + 1;
				return 0;
			}
			else if (arr[x][y] == '.') arr[x][y] = 'R';
			else arr[x][y] = 'B';
		}

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (arr[i][j] == 'R') q.push({ i, j });
				else if (arr[i][j] == 'B') arr[i][j] = '.';
			}
		}

		//print(i + 1);
	}

	arr[ax][ay] = 'I';
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << arr[i][j];
		}
		cout << "\n";
	}
}