문제
n x n 격자 위에서 펜이 이동 명령(U/D/L/R)에 따라 움직이며 선을 그린다.
수직 이동(U/D)은 세로선(|), 수평 이동(L/R)은 가로선(-)을 남기고, 둘 다 있으면 +, 없으면 .을 출력한다.
격자 범위를 벗어나는 이동은 무시한다.
입력
첫째 줄에 격자 크기 n이 주어진다. 둘째 줄에 이동 명령 문자열이 주어진다. (U/D/L/R)
출력
이동 후 n x n 격자를 출력한다. 각 칸은 +, |, -, . 중 하나이다.
예제
| 입력 | 출력 |
|---|---|
3 RDLU | +-+ / ` |
풀이
두 개의 2차원 배열로 세로선과 가로선을 독립적으로 추적하여 최종 격자를 출력하는 시뮬레이션 문제이다.
p[100][100]: 세로선(|) 표시 여부를 저장하는 배열이다.h[100][100]: 가로선(-) 표시 여부를 저장하는 배열이다.- U/D 이동 시 현재 위치와 이동 후 위치에
p배열을 true로 표시한다. - L/R 이동 시 현재 위치와 이동 후 위치에
h배열을 true로 표시한다. - 이동 전에 경계 검사를 수행하여 범위 밖이면 이동을 무시한다.
- 전체 격자를 순회하며
p[i][j]와h[i][j]값의 조합에 따라+,|,-,.을 출력한다.
핵심 아이디어: 세로선과 가로선을 별도의 배열로 분리 관리하면, 최종 출력 시 두 배열의 논리 조합만으로 각 칸의 문자를 결정할 수 있다.
코드
#include <iostream>
#include <string>
using namespace std;
int n;
string m;
bool p[100][100];
bool h[100][100];
int row, col;
bool isValidLocation(const int &row, const int &col)
{
if (row < 0 || row >= n || col < 0 || col >= n)
return false;
return true;
}
int main()
{
cin >> n;
cin >> m;
for (int i = 0; i < m.size(); i++)
{
if (m[i] == 'U')
{
if (!isValidLocation(row - 1, col))
continue;
p[row][col] = true;
p[--row][col] = true;
}
else if (m[i] == 'D')
{
if (!isValidLocation(row + 1, col))
continue;
p[row][col] = true;
p[++row][col] = true;
}
else if (m[i] == 'L')
{
if (!isValidLocation(row, col - 1))
continue;
h[row][col] = true;
h[row][--col] = true;
}
else
{
if (!isValidLocation(row, col + 1))
continue;
h[row][col] = true;
h[row][++col] = true;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (p[i][j] && h[i][j])
printf("+");
else if (p[i][j])
printf("|");
else if (h[i][j])
printf("-");
else
printf(".");
}
printf("\n");
}
return 0;
}복잡도
- 시간: O(M + N^2) (M: 명령 문자열 길이, N^2: 격자 출력)
- 공간: O(N^2)