6. 백준 C++[3495] 아스키 도형

[3495] 아스키 도형

---

 

난이도: Gold 5

시도횟수: 1

www.acmicpc.net/problem/3495

문제

창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다.

'.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이 연결된 선분을, '\'은 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점이 연결된 선분을 나타낸다.

창영이가 그린 도형의 넓이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 h와 w가 주어진다. h는 그림의 높이, w는 너비이다. (2 ≤ h,w ≤ 100)

다음 h개 줄에는 창영이가 메모장에 그린 다각형이 주어진다. 

창영이가 그린 다각형은 1개이고, 변과 변이 서로 교차하는 경우는 없고, 자기 자신과 접하는 경우도 없다.

 

---

제출한 코드

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


int main() {
	int h, w;
	int dot_num=0;
	int area = 0;
	vector<string> grid;
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		string line;
		cin >> line;
		grid.push_back(line);
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (grid[i][j] != '.' && j < w) {

				j++;
				area++;
				while (grid[i][j] == '.'&&j<w) {
					j++;
					dot_num++;

				}
				area += dot_num;
				dot_num = 0;

			}
			
			dot_num = 0;
		}

	}
	cout << area;

	return 0;
}

알고리즘이 어려워서 골드라기 보다는 기하학적인 발상이 중요했던 문제

행렬에서 가로로 쭉 search하면 하나의 행에는 적어도 한 쌍의 세로가 있기 마련이다. 또는 아예 없거나.

만약 .가 아닌 문자가 입력되면 그 순간 그 다음 /까지의 . 개수를 센다.

그러면 (.의 개수 +1)이 그 구간에서의 넓이가 된다.

 

생각해보니 지금은 while과 if로 구현했는데 stack을 이용했다면 좀 더 직관적이고 이해하기 쉬운 코드가 됐을 것 같다.

 

빨리 알고리즘의 기초 들어서 좀 풀고 싶다. 근데 이번에 논설실이랑 겹쳐서 못들을듯 ㅠ