백준 1347번 [미로 만들기](C++) -yes6686- 티스토리

백준 문제 풀이: 1347 [미로 만들기]

---

문제 링크: https://www.acmicpc.net/problem/1347

문제 설명:

길이가 n인 문자열이 주어지며, 문자열을 따라 미로를 탐색하면서 길을 생성해야 합니다. 방향 전환 및 이동 규칙은 다음과 같습니다:

• 'F': 현재 방향으로 전진
• 'R': 오른쪽으로 90도 회전
• 'L': 왼쪽으로 90도 회전

초기 방향은 남쪽이며, 탐색이 끝난 후 미로의 최소 크기를 출력해야 합니다.

---

문제 해결 코드

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

int map[101][101]; // 미로 맵
int n; // 입력 문자열 길이

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    string s;
    cin >> s;

    // 방향 설정 (동: 0, 남: 1, 서: 2, 북: 3)
    int dx[4] = { 0, 1, 0, -1 };
    int dy[4] = { 1, 0, -1, 0 };

    int x = 50, y = 50, d = 1; // 시작 위치 (남쪽 방향)
    map[x][y] = 1;

    int minX = 50, minY = 50, maxX = 50, maxY = 50;

    // 문자열을 따라 미로 생성
    for (char c : s) {
        if (c == 'R') {
            d = (d + 1) % 4; // 시계 방향 회전
        } else if (c == 'L') {
            d = (d + 3) % 4; // 반시계 방향 회전
        } else { // 'F'
            x += dx[d];
            y += dy[d];
            map[x][y] = 1;
            minX = min(minX, x);
            minY = min(minY, y);
            maxX = max(maxX, x);
            maxY = max(maxY, y);
        }
    }

    // 미로 출력
    for (int i = minX; i <= maxX; i++) {
        for (int j = minY; j <= maxY; j++) {
            cout << (map[i][j] ? "." : "#");
        }
        cout << '\n';
    }

    return 0;
}

예제 입력:

7
RRFRFFL

예제 출력:

...
.##

---

코드 설명

• 핵심 알고리즘: 시뮬레이션을 통해 주어진 문자열을 따라 미로를 생성합니다.
• 구현 세부사항:
  • 방향을 나타내는 배열 dx, dy를 활용하여 회전을 쉽게 구현합니다.
  • 미로의 시작 위치를 (50, 50)으로 설정하여 이동할 공간을 확보합니다.
  • 최소한의 영역을 출력하기 위해 minX, minY, maxX, maxY를 추적합니다.
• 시간 복잡도: O(n) (문자열을 한 번 순회하면서 미로를 생성)

---

결과

입력된 문자열을 따라 미로를 정확히 구성하고, 최소 크기로 출력합니다. 시뮬레이션 문제 해결 및 방향 전환 로직을 연습하는 데 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!