[BOJ] 1347. 미로 만들기

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

1347번: 미로 만들기

문제에서 홍준이는 자기의 움직임을 모두 적는다. 홍준이가 적은 내용의 길이 N이과 그 내용이 주어진다.

미로가 몇 칸인지 알 수 없으므로 미로를 만들 배열의 크기를 101*101로 잡았다.

문제에서 N이 0보다 크고 50보다 작다고 했으므로 상하좌우 어떤 방향이든 한 방향으로만 가는 경우(가장 멀리 가는 경우)를 생각해서 넉넉하게 잡았다.

 

 

시작점은 배열의 가운데 쯤인 50,50에서 시작하면서 적은 내용에 맞게 움직인다.

처음에 남쪽을 바라보고 있다고 했으므로 처음 방향은(1,0)이다.

방향 전환을 쉽게 할 수 있도록 dx, dy배열에 남쪽에서부터 시계방향 순서로(반대도 상관없다) 방향을 저장해 둔다.

R 인 경우 오른쪽으로 방향을 전환하므로 dir+1을 해주면 되지만 3번째는 index를 넘어가버리기 때문에 % 연산을

이용하여 (dir+1) % 4를 해주면 된다.

마찬가지로 L은 왼쪽 방향으로 회전하므로 dx, dy배열의 앞의 칸으로 이동하기 위해 (dir+3) % 4를 해주면 된다.

 

 

가장 중요한 직사각형 미로를 출력해주기 위해서 직사각형의 시작점과 끝점을 알아야 한다.

시작점과 끝점을 홍준이의 시작 위치(50,50)로 잡아두고 이동할 때마다 비교해서

x, y의 최솟값(왼쪽 맨 위)이 시작점, x,y의 최댓값(오른쪽 맨 아래)이 끝점이 되도록 해준다.

 

 

그러면 내용대로 모두 움직인 후에 직사각형 범위만큼을 출력해주면 되는데

. 이 없는 경우에 #을 출력하면 된다.

#include <iostream>
#include <string>
using namespace std;
 
 
int n;
string s;
char map[101][101];
 
//남,서,북,동 순서
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
 
 
void solve() {
    //직사각형의 왼쪽 위 좌표(sx,sy)와 오른쪽 아래 좌표(ex,ey)
    int sx = 50;
    int sy = 50;
    int ex = 50;
    int ey = 50;
 
 
    //시작점을 가운데 칸으로 설정
    int x = 50;
    int y = 50;
    int dir = 0;
    map[x][y] = '.';
 
 
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') {
            //오른쪽으로 방향 회전
            dir = (dir + 1) % 4;
        }
        else if (s[i] == 'L') {
            //왼쪽으로 방향 회전
            dir = (dir + 3) % 4;
        }
        else if (s[i] == 'F') {
            //앞으로 이동
            x += dx[dir];
            y += dy[dir];
            map[x][y] = '.';
 
 
            //이동한 경우 직사각형의 좌표와 비교해준다.
            if (x < sx) sx = x;
            if (y < sy) sy = y;
            if (x > ex) ex = x;
            if (y > ey) ey = y;
        }
 
        
    }
 
 
    //직사각형을 출력
    // '.' 이 아닌 경우에는 벽이므로 '#'을 출력
    for (int i = sx; i <= ex; i++) {
        for (int j = sy; j <= ey; j++) {
            if (map[i][j] == '.')
                cout << map[i][j];
            else
                cout << '#';
        }
        cout << '\n';
    }
 
    
 
}
 
int main() {
 
    cin >> n;
    cin >> s;
 
    solve();
    
    return 0;
}