백준 14890 - 경사로

문제 링크입니다 https://www.acmicpc.net/problem/14890

14890번: 경사로

 

길이 주어졌을때 다음과 같은 방식으로 경사로가 만들어집니다. 

 

그림에서 위 경우에는 높이 차가 1이며, 경사로를 놓을 수 있는 구간 길이가 2이상이기에 경사로를 설치할 수 있습니다.

아래 경우에서는 1번 그림에서는 높이 차가 2이기 때문에

                      2번 그림에서는 경사로가 바닥에 닿아있지 않기 때문에

                      3번 그림에서는 경사로가 곂쳐서 놓였기 때문에

                      4번 그림에서는 기울여졌기 때문에 경사로를 놓지 못합니다.

 

 

왼쪽 그림과 같이 입력이 주어졌다면, 오른쪽 그림의 파란색 부분만 경사로를 놓을 수 있습니다.

 

접근 방법

 

1. 행과 열을 따로 계산한다.

2. 행의 경우

   2-1. 현재 칸과 다음 칸의 높이가 같다면 다음 칸으로 넘어간다

   2-2. 현재 칸과 다음 칸의 높이 차가 1이라면 L의 길이만큼 경사로를 놓을 수 있는지 탐색한다.

   2-3. 현재 칸과 다음 칸의 높이 차가 2이상이라면 해당 경우는 놓지 못한다.

3. 열의 경우는 행의 경우와 같은 논리로 찾습니다. 

 

2-1의 높이가 같은 경우는 그냥 넘어가면 되기에 간단합니다.

2-2의 높이 차가 1인 경우가 구현하기 어려운 편이였습니다. 저의 경우에는 해당 열이나 행의 상태를 알 수 있는 배열 하나를 선언했습니다. 배열에 1의 값이 저장되면 경사로가 놓인 곳, 아니면 경사로가 놓이지 않은 곳입니다.

높이 차가 1인 경우가 다음 칸이 클 경우, 다음 칸이 작은 경우입니다.

각각의 경우를 나누어서 L만큼 놓을 수 있는지 탐색한 뒤, 놓을 수 없다면 해당 줄은 경사로를 만들 수 없다고 해줍니다. 만약 놓을 수 있다면 해당 칸들의 배열을 1로 바꾸어주고 다음 칸 탐색을 계속합니다.

 

 

자세한 것은 코드를 참고해 주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int N, L;
int miro[101][101];
int can_make;

void col() {
	for (int i = 1; i <= N; i++) {			
		int check[101];
		memset(check, 0, sizeof(check));
		for (int j = 1; j <= N; j++) {
			if (j == N) {
			//	cout << i << "\n";
				can_make++;
				continue;
			}
			if (miro[i][j] == miro[i][j+1] && j+1 <= N) {
				//cout << i << " " << j << "\n";
				//cout << miro[i][j] << " " << miro[i][j+1] << "\n\n";
				continue;
			}
			else if (miro[i][j] - miro[i][j+1] == 1) {
				if (check[j + 1] == 1) j = N + 1;
				int cnt = 1;
				check[j + cnt] = 1;
				while (1) {						
				//	cout << i << " " << cnt << "down\n";
					if (cnt == L) {
						break;
					}
					if (miro[i][j+1+cnt] == miro[i][j] - 1 && check[j + 1 + cnt] == 0 && j + 1 + cnt <= N) {
						check[j + 1 + cnt] = 1;
						cnt++;
					}
					else if (miro[i][j+1+cnt] != miro[i][j] - 1 || check[j + 1 + cnt] == 1 || j + 1 + cnt > N) {
						break;
					}
				}
				if (cnt == L) {
					j += cnt-1;
					continue;
				}
				else {
					j = N + 1;
				}
			}
			else if(miro[i][j+1] - miro[i][j] == 1){
				if (check[j] == 1) j = N + 1;
				int cnt = 1;
				check[j] = 1;
				while (1) {		
				//	cout << i << " " << cnt << "up\n";
					if (cnt == L) {
						break;
					}
					if (miro[i][j-cnt] == miro[i][j+1] - 1 && check[j - cnt] == 0 && j - cnt >= 1) {
						check[j -cnt] = 1;
						cnt++;
					}
					else if (miro[i][j-cnt] != miro[i][j+1] - 1 || check[j - cnt] != 0 || j- cnt < 1) {	
						break;
					}
				}
				if (cnt == L) {
					continue;
				}
				else {
					j = N + 1;
				}
			}
			else if (abs(miro[i][j] - miro[i][j+1]) > 1) {
				j = N + 1;
			}
		}
	}
}

void row() {
	for (int i = 1; i <= N; i++) {			
		int check[101];
		memset(check, 0, sizeof(check));
		for (int j = 1; j <= N; j++) {
			if (j == N) {
			//	cout << i << "\n";
				can_make++;
				continue;
			}
			if (miro[j][i] == miro[j + 1][i]&& j+1 <= N) {
				//cout << j << " " << i << "\n";
				//cout << miro[j][i] << " " << miro[j+1][i] << "\n\n";
				continue;
			}
			else if (miro[j][i] - miro[j + 1][i] == 1) {
				if (check[j + 1] == 1) j = N + 1;
				int cnt = 1;
				check[j + cnt] = 1;
				while (1) {						
				//	cout << i << " " << cnt << "down\n";
					if (cnt == L) {
						break;
					}
					if (miro[j +1+ cnt][i] == miro[j][i] - 1 && check[j + 1 + cnt] == 0 && j + 1 + cnt <= N) {
						check[j + 1 + cnt] = 1;
						cnt++;
					}
					else if (miro[j + 1 + cnt][i] != miro[j][i] - 1 || check[j + 1 + cnt] == 1 || j + 1 + cnt > N) {
						break;
					}
				}
				if (cnt == L) {
					j += cnt-1;
					continue;
				}
				else {
					j = N + 1;
				}
			}
			else if(miro[j+1][i] - miro[j][i] == 1){
				if (check[j] == 1) j = N + 1;
				int cnt = 1;
				check[j] = 1;
				while (1) {		
				//	cout << i << " " << cnt << "up\n";
					if (cnt == L) {
						break;
					}
					if (miro[j - cnt][i] == miro[j+1][i] - 1 && check[j - cnt] == 0 && j - cnt >= 1) {
						check[j -cnt] = 1;
						cnt++;
					}
					else if (miro[j- cnt][i] != miro[j+1][i] - 1 || check[j - cnt] != 0 || j- cnt < 1) {	
						break;
					}
				}
				if (cnt == L) {
					continue;
				}
				else {
					j = N + 1;
				}
			}
			else if (abs(miro[j][i] - miro[j + 1][i]) > 1) {
				j = N + 1;
			}
		}
	}
}

void solve() {
	row(); //행
	col(); //열
	cout << can_make;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> L;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> miro[i][j];
		}
	}

	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요