[C++]미로 만들기 1347

문제

홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다.

입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다.

입력

첫째 줄에 홍준이가 적은 내용의 길이가 주어진다. 길이는 0보다 크고, 50보다 작다. 둘째 줄에 홍준이가 적은 내용이 내용이 주어진다.

출력

첫째 줄에 미로 지도를 출력한다. ‘.’은 이동할 수 있는 칸이고, ‘#’는 벽이다.

알고리즘 분류

• 구현
• 시뮬레이션

---

분석

입력 길이는 50보다 작다. 즉, F가 50개 나와도 최대 가로/세로 길이는 50 이하가 된다.

때문에 2차원 배열을 arr[100][100]로 선언하고, 시작점을 arr[50][50]으로 설정하면 오버플로우가 발생하지 않게 된다.

배열에서 이동할 수 있는 칸이라면 1을 할당해줄 것이다.

회전

회전에 대한 정보도 기억해야 할 것이다. 처음에는 남쪽을 바라보고 있으므로 남쪽은 숫자 0이라고 하자.

• 남: 0
• 서: 1
• 북: 2
• 동: 3

int dir = 0;
///
if (opt == 'R') dir = (dir + 5) % 4;
else if (opt == 'L') dir = (dir + 3) % 4;

이동

현재의 수직좌표를 v, 수평좌표를 h라 하자.

else if (opt == 'F') {
	switch (dir)
	{
	case 0:
		v++;
		break;
	case 1:
		h--;
		break;
	case 2:
		v--;
		break;
	case 3:
		h++;
		break;
	}
	arr[v][h] = 1;
}

미로 그리기

이렇게 모든 수행에 대해 이동할 수 있는 칸에 대한 정보를 얻었다면, 어떻게 문제 조건에 맞는 미로의 좌표 및 크기를 구할 수 있을까?

이를 해결하기 위해서 각각의 좌표에 대해 최댓값과 최솟값 정보를 알고 있어야 한다. 선언 시 시작점인 50으로 초기화해준다.
F가 입력될 때마다 v 혹은 h의 값이 변하는 걸 확인할 수 있다.
이때마다 최댓값과 최솟값을 저장해줘야 한다.

v_min = min(v_min, v);
v_max = max(v_max, v);
h_min = min(h_min, h);
h_max = max(h_max, h);

이렇게 되면, 수직좌표의 범위는 v_min부터 v_max, 수평좌표의 범위는 h_min부터 h_max라는 것을 알 수 있다.

전체코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
int n, dir = 0; // 0남 1서(R) 2북 3동
int v, h; // 세로 가로 현재위치
int v_max, v_min, h_max, h_min;
char opt;
int arr[101][101];


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	v = h = v_max = v_min = h_max = h_min = 50;
	arr[50][50] = 1; // 시작점
	while (n--) {
		cin >> opt;
		if (opt == 'R') dir = (dir + 5) % 4;
		else if (opt == 'L') dir = (dir + 3) % 4;
		else if (opt == 'F') {
			switch (dir)
			{
			case 0:
				v++;
				break;
			case 1:
				h--;
				break;
			case 2:
				v--;
				break;
			case 3:
				h++;
				break;
			}
			arr[v][h] = 1;
		}
		v_min = min(v_min, v);
		v_max = max(v_max, v);
		h_min = min(h_min, h);
		h_max = max(h_max, h);
	}
	for (int i = v_min; i <= v_max; i++) {
		for (int j = h_min; j <= h_max; j++) {
			cout << (arr[i][j] ? '.' : '#');
		}
		cout << "\n";
	}
	return 0;
}