백준 1347번 미로 만들기 C++

백준 1347번 미로 만들기 C++ 풀이

문제

홍준이는 미로 안의 한 칸에서 남쪽을 바라보고 서 있습니다.

홍준이가 움직이는 방법은 다음과 같습니다.

• F: 현재 바라보는 방향으로 앞으로 한 칸 전진
• L: 현재 방향에서 왼쪽으로 90도 회전
• R: 현재 방향에서 오른쪽으로 90도 회전

이동 경로가 문자열로 주어집니다.

홍준이가 지나간 칸은 모두 .(점)으로 표시합니다.

홍준이가 가지 않은 칸은 모두 #(샵)으로 표시합니다.

최종적으로 홍준이가 지나간 모든 칸이 포함된 최소 직사각형 범위만 잘라서 미로 지도를 출력합니다.

테스트 케이스 예시

입력

5
RRFRF

과정

1. 시작: (0,0)에서 남쪽을 보고 시작
2. R → 서쪽, R → 북쪽, F → (-1,0) 이동, R → 동쪽, F → (-1,1) 이동
3. 방문 좌표: (0,0), (-1,0), (-1,1)
4. 최소 행 = -1, 최대 행 = 0 / 최소 열 = 0, 최대 열 = 1
5. 지도 크기 = 2행 × 2열
6. 방문한 칸 . 표시, 나머지는 # 표시

출력

..
.#

---

아이디어

1. 방향 관리

먼저 홍준이가 어느 방향을 보고 있는지를 관리해야 합니다. 홍준이는 처음에 남쪽을 보고 시작합니다. 방향을 숫자로 약속하고, index라는 변수를 두어 0~3 사이로 방향을 가리키게 합니다. 각 방향에 따라 좌표가 어떻게 변하는지는 dx, dy 배열로 나타냅니다.

       북 (index = 2)
       (0,-1)

서 (index = 1)        동 (index = 3)
(-1,0)               (1,0)

       남 (index = 0)
       (0,1)

이를 코드로 나타내면 다음과 같습니다.

int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

회전 규칙

• R 명령: 오른쪽(시계 방향) 회전 = index를 +1
• L 명령: 왼쪽(반시계 방향) 회전 = index를 -1
• index가 0~3을 벗어나면, 모듈로 연산(\((index+4)\%4\))으로 맞춰줍니다.

2. 좌표 이동 시뮬레이션

방향 관리가 준비되었으니 문자열을 읽으며 시뮬레이션을 합니다. 홍준이는 처음에 (0,0)에서 시작합니다.

초기 상태:

현재 위치: (0,0)
현재 방향: 남쪽 (index = 0)

문자열의 문자 하나하나를 처리합니다.

• L: 방향만 바뀝니다. 위치 변화 없음.
• R: 방향만 바뀝니다. 위치 변화 없음.
• F: 현재 방향에 따라 (x+dx[index], y+dy[index])로 좌표를 바꿉니다.

예를 들어 입력 문자열이 "RRFRF"라면 다음과 같은 변화가 생깁니다.

1. R → 남쪽(index=0)에서 오른쪽 회전 → 서쪽(index=1), 위치는 그대로 (0,0)
2. R → 서쪽(index=1)에서 오른쪽 회전 → 북쪽(index=2), 위치는 그대로 (0,0)
3. F → 북쪽(index=2) → (0+dx[2], 0+dy[2]) = (0,0+(-1)) = (0,-1), 방문 좌표에 (0,-1) 추가
4. R → 북쪽(index=2)에서 오른쪽 회전 → 동쪽(index=3), 위치 그대로 (0,-1)
5. F → 동쪽(index=3) → (0+1, -1+0) = (1,-1), 방문 좌표에 (1,-1) 추가

최종 방문 좌표는 (0,0), (0,-1), (1,-1)이 됩니다.

3. 최소/최대 좌표 구하기

시뮬레이션을 마치면 방문 좌표들이 여러 개 생깁니다. 예: (0,0), (0,-1), (1,-1)

이 좌표들에서 최소 x, 최대 x, 최소 y, 최대 y를 찾습니다.

• 최소/최대 x: 세로(행) 범위를 결정
• 최소/최대 y: 가로(열) 범위를 결정

예제 "RRFRF"의 경우:

• x좌표들 = {0, 0, 1} → 최소 0, 최대 1
• y좌표들 = {0, -1, -1} → 최소 -1, 최대 0

따라서 미로 크기:

• 행 수 = max_x - min_x + 1 = 1 - 0 + 1 = 2
• 열 수 = max_y - min_y + 1 = 0 - (-1) + 1 = 2

즉, 2×2 배열만 있으면 충분합니다.

4. 음수 좌표 보정

음수 좌표가 있으므로, 이를 배열 인덱스로 바로 사용할 수 없습니다.

이때 사용하는 방법은 보정(offset)입니다.

• 보정값 = -min_x, -min_y
• 모든 좌표에서 min_x, min_y를 빼주면 최소값이 0이 됩니다.

예시 "RRFRF"에서:

• min_x = 0, min_y = -1
• 보정 후 좌표 = (x - min_x, y - min_y)

계산해보면:

• (0,0) → (0-0, 0-(-1)) = (0,1)
• (0,-1) → (0-0, -1-(-1)) = (0,0)
• (1,-1) → (1-0, -1-(-1)) = (1,0)

즉, 전부 0 이상이 되어 배열 인덱스로 안전하게 사용할 수 있습니다.

5. 지도 출력

배열 크기만큼 2차원 배열을 만듭니다.

• 기본은 전부 #로 채웁니다.
• 보정된 좌표 위치에 .을 찍습니다.

보정된 좌표: (0,1), (0,0), (1,0)

2×2 배열을 채우면:

..
.#

• 첫 줄 (y=0): (0,0)과 (1,0) → ..
• 둘째 줄 (y=1): (0,1)만 방문 → .#

---

정리

1. 방향 관리: index와 dx, dy 배열로 방향을 단순화
2. 좌표 시뮬레이션: 문자열을 읽으면서 좌표 이동
3. 최소/최대 좌표 찾기: 전체 지도의 크기 결정
4. 음수 보정: 모든 좌표를 0 이상으로 변환
5. 지도 출력: 기본 #에서 방문한 곳만 . 찍기

이 다섯 단계로 문제를 풀면 어떤 입력이든 올바른 미로 지도를 출력할 수 있습니다.

---

전체 코드

아래는 구현한 전체 코드입니다. 동적 배열을 사용했지만 STL 벡터로도 바꿀 수 있습니다. 좌표 기록, 방향 회전, min/max 계산, 보정, 지도 출력까지 포함되어 있습니다.

#include #include #include #include using namespace std; // 북, 서, 남, 동 방향 (여기서는 문제 조건에 맞게 바꾸어도 됨) int dx[4]={0,-1,0,1}; int dy[4]={1,0,-1,0}; struct Point{ int x; int y; }; // 좌표 출력용 (디버깅할 때 사용 가능) ostream& operator<<(ostream& os, const Point& p) { os << "(" << p.x << ", " << p.y << ")"; return os; } int direction=0; // 시작 방향 (남쪽) int main(void) { int N,cnt=1; cin>>N; char* arr= new char[N+1]; Point* lst=new Point[N+1]; for(int i=0;i>arr[i]; } Point current={0,0}; lst[0]=current; int idx=1; // 이동 시뮬레이션 for(int i=0;imax_x) max_x=lst[i].x; if(lst[i].ymax_y) max_y=lst[i].y; } int row=max_y-min_y+1; int col=max_x-min_x+1; // 지도 생성 및 초기화 char miro[55][55]; for(int i=0;i

---

결론

이 문제를 풀면서 얻은 핵심 포인트는 다음 네 가지입니다.

1. 방향 관리: L, R을 회전으로 바꿔주는 로직을 정확히 짜야 합니다.
2. 좌표 기록: 단순히 마지막 좌표만이 아니라 모든 방문 좌표를 기록해야 합니다.
3. 음수 보정: 방문 좌표가 음수일 수 있으므로 min_x, min_y를 이용해 0 이상으로 맞춥니다.
4. 최소 직사각형 출력: 실제로 방문한 영역만큼만 잘라내어 출력해야 올바른 답이 됩니다.