191006 백준 알고리즘 문제풀기

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <cmath>
#include <algorithm>

using namespace std;

int map_a[100][100]; // 가로 맵 저장용
int map_b[100][100]; // 세로 맵 저장용

bool flat(int arr[], int s, int d) // 인덱스 s부터 d까지 평평한가(그래야 경사로를 둘 수 잇음)
{ // s: start index, d: dest index
	int cnt = 0;
	for (int i = s; i < d; i++)
	{
		if (arr[i] - arr[i + 1] != 0)
		{
			cnt++;
		}
	}
	if (cnt == 0)
		return true; // 평평하면 true 반환
	else
		return false; // 아니면 false 반환
}

bool stair(int arr[], int s, int d) // s부터 d까지 계단 세울 수 있는가 (계단이 존재하지 않아야 함)
{
	int cnt = 0;
	for (int i = s; i <= d; i++)
	{
		if (arr[i] == 2)
			cnt++;
	}
	if (cnt == 0)
		return true;
	else
		return false;
}


void make_stair(int check[], int s, int d) // 계단을 세운다.
{
	for (int i = s; i <= d; i++)
	{
		check[i] = 2;
	}
}

bool checker(int arr[], int w, int l)
{
	int check[100]; // check 배열엔 지나간 경우는 1, 경사로 세운 경우는 2, 못 지나간 경우는 0으로 표시
	std::fill_n(check, w, 0); // check배열 0으로 초기화

	for (int i = 0; i < w; i++)
	{ // 전체 배열에 대해서
		if (i == w - 1)
		{ // 마지막 인덱스까지 왔다면 앞 인덱스의 조건은 모두 통과한 경우다.
			check[i] = 1; // 따라서 1로 채운다.
			break;
		}
		if (arr[i] == arr[i + 1])
		{//다음칸과 높이가 같은 경우
			if (check[i] == 0) // 만약 현재 위치에 경사로가 존재하지 않는다면
				check[i] = 1; // 지나간다.
			else
				continue; // 경사로가 존재한다면 넘어간다.(경사로 중복 방지)
		}
		else if (arr[i] < arr[i + 1] && arr[i + 1] - arr[i] == 1)
		{//다음칸이 높고 1 차이나는 경우
			int sx = i - l + 1; // 경사로 처음 좌표
			int dx = i; // 경사로 마지막 좌표
			if (0 <= sx && flat(arr, sx, dx) && stair(check, sx, dx))
			{//이전에 길이가 충분하고, 경사로 구간이 평평하며, 경사로 구간에 다른 경사로가 존재하지 않다면
				make_stair(check, sx, dx);//해당 구간 경사로를 만든다.
			}
			else break; // 아니라면 break(뒤 쪽 볼 필요 없음)
		}
		else if (arr[i] > arr[i + 1] && arr[i] - arr[i + 1] == 1)
		{//다음칸이 낮고 1 차이나는 경우
			int sx = i;
			int dx = i + l;
			if (dx < w && flat(arr, sx + 1, dx) && stair(check, sx + 1, dx))
			{//다음에 경사로를 둘 길이가 충분하고, 경사로 구간이 평평하며, 경사로 구간에 다른 경사로가 존재하지 않다면
				check[i] = 1; // 현재 위치를 1로 초기화(지나갔으므로)
				make_stair(check, sx + 1, dx); // 경사로를 둔다.
				i = dx - 1; // index를 경사로 마지막 위치로 초기화한다.(중복으로 for문 돌을 필요 없음)
			}
			else break; // 아니라면 break(뒤쪽 볼 필요 없음)
		}
		else // 아닌 경우 무조건 갈 수 없음
			break;
	}
	
	//갈 수 있는지 check
	bool go = true;
	for (int i = 0; i < w; i++)
	{
		if (check[i] == 0)
			go = false; // 만약 끝까지 못간경우 false반환
	}

	return go;
}

int main()
{
	int N, L;
	scanf("%d %d", &N, &L);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map_a[j][i]); // 가로 방향 입력
			map_b[i][j] = map_a[j][i]; // 세로 방향 초기화
		}
	}

	int ans = 0;
	for (int j = 0; j < N; j++)
	{
		ans += checker(map_a[j], N, L); // 가로 방향 계산
	}
	for (int j = 0; j < N; j++)
	{
		ans += checker(map_b[j], N, L); // 세로 방향 계산
	}

	printf("%d\n", ans);
	
	//system("pause");
	return 0;
}

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

int map[101][101]; // 맵 저장용
int check[101][101]; // 맵 중간 계산용 (동일 좌표 내에서)
int temp[101][101]; // 맵 중간 계산용 (회전시)

int dx[] = { 1,0,-1,0 }; // 각각 0, 1, 2, 3에 대한 이동 매핑
int dy[] = { 0,-1,0,1 };

int answer = 0; // 정답

vector<tuple<int, int, int, int>> dots; // x, y, d, g 저장용
void rotate(int &sx, int &sy, int &cx, int &cy, int N); // 회전 함수
void calc_map(int n); // 점수 계산 함수

void make_map(int n)
{
	for (int i = 0; i < dots.size(); i++)
	{ // 각 x, y, d, g 좌표에 대해
		memset(check, 0, sizeof(check)); // check 배열 초기화
		memset(temp, 0, sizeof(check)); // temp 배열 초기화

		int sx, sy, d, g;
		tie(sx, sy, d, g) = dots[i]; // x, y, d, g 저장
		map[sy][sx] = 1; // 최종 저장 맵용 시작좌표 check
		check[sy][sx] = 1; // 이번 turn 계산용 시작좌표 check

		int nx, ny;
		nx = sx + dx[d]; // 마지막 좌표 저장
		ny = sy + dy[d];
		if (0 <= nx && nx < n && 0 <= ny && ny < n)
		{ // 마지막 좌표가 범위를 벗어나지 않는다면
			map[ny][nx] = 1; // 최종 저장 맵용 check
			check[ny][nx] = 1; // 이번 turn 계산용 check
			while (g--)
			{ // 회전 횟수만큼 회전
				rotate(sx, sy, nx, ny, n); // 회전
			} // 위 함수에서 while 문 내의 nx, ny가 초기화됨.(회전중심점)
		}
		else continue;
	}
}

void calc_map(int n)
{
	int sum = 0;
	for (int j = 0; j < n - 1; j++)
	{
		for (int i = 0; i < n - 1; i++)
		{
			sum = 0;
			for (int y = 0; y < 2; y++)
			{
				for (int x = 0; x < 2; x++)
				{
					if (map[j + y][i + x] > 0)
					{
						sum++; // 해당 좌표에 값이 저장되어있으면 더하고
					}
				}
			}
			if (sum >= 4)
			{
				answer++; // 4 이상 저장되었으면 정답
			}
		}
	}
}

void rotate(int &sx, int &sy, int &cx, int &cy, int N)
{
	int rx, ry;
	int nsx, nsy;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			temp[i][N - 1 - j] = check[j][i]; // 오른쪽으로 90도 회전한다.
			if (j == cy && i == cx)
			{ // 만약 현재 인덱스가 회전 중심점이라면
				rx = N - 1 - j; // 변경된 회전 중심점을 각각 rx, ry에 저장
				ry = i;
			}
			if (j == sy && i == sx)
			{ // 만약 현재 인덱스가 시작점이라면
				nsx = N - 1 - j; // 변경된 시작점을 저장
				nsy = i; // 변경된 시작점은 다음 generation이 붙는데 사용됨
			}
		}
	}

	int dx, dy; // 이동 자리 값
	dx = cx - rx;
	dy = cy - ry;
	nsx += dx; // 변경 시작점에 이동값을 더해서 최종 완성
	nsy += dy;

	//원래에 붙이기
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			int ny = j + dy;
			int nx = i + dx;
			if (0 <= nx && nx < N && 0 <= ny && ny < N)
			{ // 범위를 벗어나지 않는다면
				if (check[ny][nx] == 0 && temp[j][i] != 0)
				{
					check[ny][nx] += temp[j][i]; // 현재 좌표 계산용 check맵에 초기화
					map[ny][nx] += temp[j][i]; // 결과값용 map도 초기화
				}
				else
				{ // 범위 벗어나지 않는다면 넘어간다.
					continue;
				}
			}
		}
	}
	cx = nsx; // 회전 중심점을 새로운 중심점으로 초기화
	cy = nsy;
}


int main()
{
	int N;
	scanf("%d", &N);
	int x, y, d, g;
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d %d %d", &x, &y, &d, &g);
		dots.push_back(make_tuple(x, y, d, g));
	}

	make_map(101); // 맵 만들고
	calc_map(101); // 정답 계싼
	
	printf("%d\n", answer);

	//system("pause");
	return 0;
}