문제
/와 \ 문자로 이루어진 아스키 아트 그리드가 주어질 때, 도형 내부의 넓이를 구하는 문제다. 각 슬래시 문자는 격자 칸의 절반(0.5 넓이)을 차지하며, 슬래시로 둘러싸인 내부의 점(.)은 넓이 1을 기여한다.
입력
- 첫 줄에 H와 W가 주어진다.
- 이후 H줄에 걸쳐 W개의 문자(
/,\,.)로 이루어진 그리드가 주어진다.
출력
- 도형 내부의 넓이를 정수로 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 4 \/\/ \/\/ | 2 |
풀이
각 행을 스캔하며 슬래시의 홀짝성으로 내부/외부를 판단하는 방식으로 넓이를 계산한다.
- 각 행을 왼쪽에서 오른쪽으로 순회한다.
/또는\를 만날 때마다 슬래시 카운터를 증가시키고 넓이에 1을 더한다 (각 슬래시는 0.5 넓이 × 2)..을 만날 때 슬래시 카운터가 홀수이면 도형 내부이므로 넓이에 2를 더한다 (나중에 2로 나눔).- 최종 누적값을 2로 나눠 실제 넓이를 출력한다.
핵심 아이디어: 슬래시 문자의 홀짝성(parity)으로 현재 위치가 도형 내부인지 외부인지 판단한다. 모든 계산을 2배 스케일로 진행한 후 마지막에 2로 나눠 정수 결과를 얻는다.
코드
#include <iostream>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair<int, int>
char arr[101][101];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int H, W;
int result = 0;
cin >> H >> W;
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
cin >> arr[i][j];
}
}
for (int i = 0; i < H; i++)
{
int cnt = 0;
for (int j = 0; j < W; j++)
{
if (arr[i][j] == '/' || arr[i][j] == '\\') // 괄호당 넓이 0.5
{
cnt++; // 슬래쉬 갯수
result += 1;
}
if (cnt % 2 && arr[i][j] == '.')
result += 2; // 열려있으면 점 갯수 세기
}
}
cout << result / 2;
return 0;
}복잡도
- 시간: O(H × W) — 그리드의 모든 셀을 한 번씩 순회
- 공간: O(H × W) — 그리드 저장 배열