[삼성코테기출문제] 경사로

경사로

문제

시뮬레이션 문제이다. 단순히 보면 쉬운 문제로 착각하기 쉽다. 그냥 행이나 열로 처음부터 끝까지 갈 수 있냐? 갈 수 없으면 주어진 경사로를 놓아라, 경사로를 놓지 못하거나 놓아도 갈 수 없는 길이면 지나갈 수 없는 길이다.
하지만 경사로를 놓는 조건을 구현하는 것이 생각보다 까다로웠다. 처음에 문제를 풀 때 생각한 조건을 구현하고 빠진 조건이 있으면 추가하면서 하니 코드가 너무 길어졌다. 물론 답도 나오지 않았다. 시뮬레이션문제는 이런 부분이 어려운 것 같다, 빠진 조건을 추가하다보면 코드가 꼬이는 일이 생기고 결국 시간 안에 문제를 풀지 못하는…
물론 많은 연습이 있다면 나아지겠지만 아직까진 좀 부족한것 같다.

문제 풀이

이 문제는 다시 풀으라고하면 힘들것 같다. 풀다가 안풀려서 다 지우고 모든 조건을 다시 생각해가며 코드를 짯다. 이 문제의 keypoint는 경사로에 대한 조건을 잘 생각해서 예외가 일어나지 않게 짜는 것이 중요한 것 같다.

입출력 조건

풀이 과정

1. 맵에 대한 정보를 받고 행에 대해서 탐색할 것인지, 열에 대해서 탐색할 것인지를 판단하여 행이면 true를 넘겨주고 열이면 false를 넘겨주어서 탐색을 시작한다.
   slope(int i, bool c)에서 bool은 행이냐? 열이냐?를 의미하고, i는 몇번째냐?를 의미한다.
2. 해당 길에 한 칸 들어왔으므로 cnt는 1부터 시작하고, 다음 칸을 의미하는 j로 반복문을 이용하여 한 칸 한 칸 탐색한다.
3. d는 현재 칸과 다음 칸을 행과 열에 따라 계산하여 받는 변수 이다. 이 때 d의 조건으로 경사로를 세울 수 있냐? 경사로를 세우는 중이냐? 를 판단할 것이다.
   • d=0이면 현재 칸과 다음 칸의 차이가 없으므로 움직일 수 있다. 따라서 한 칸 움직였다는 의미인 cnt를 1증가 시켜준다.
   • d=1 and cnt >= L이면 현재 칸과 다음 칸의 차이는 1이고 다음 칸이 더 높다는 뜻이다. 따라서 현재까지 지나온 길이 경사로의 길이(L)보다 같거나 길어야 경사로를 세울 수 있으므로 cnt>=L의 조건도 같이 확인한다.
   • d=-1 and cnt>=0이면 현재 칸과 다음 칸의 차이는 -1이고 다음 칸이 더 낮다는 뜻이다. 따라서 다음 칸들이 계속해서 갈 수 있는 길이어야한다. 그리고 아직 다음 칸으로 넘어가지 않았으므로 cnt>=0이어야 한다.
   • else 나머지인 경우는 경사로를 세울 수 없으므로 현재 재귀함수를 종료한다.
   • 예를 들어보자.
     L=2, 2233223 인 길이 있다. 현재 칸(이하 c), 다음 칸(이하 n),갈 수 있으면 OK, 못 가면 NO라고 할 때
     c=2, n=2, d=0, cnt=1 OK cnt++
     c=2, n=3, d=1, cnt=2 (cnt>=L에 만족) OK cnt=1
     c=3, n=3, d=0, cnt=1 OK cnt++
     c=3, n=2, d=-1,cnt=2 (cnt>=0에 만족 일단 내려가는 경사로를 세움) cnt = -L+1 -> cnt=-1
     c=2, n=2, d=0, cnt=-1 (경사로를 세우는 중)cnt++
     c=2, n=3, d=1, cnt=0 (d=1 and cnt >= L에 만족하지 못 함)NO
     내려가는 경사로를 음수를 이용하여 계산하여 경사로를 다 세우면 cnt=0이 되게하여 다음 경사로를 생각해준다 따라서 이 길은 갈 수 없는 길이다.
     만약 이 길이 223322223이라면 (d=1 and cnt >= L에 만족하므로) OK가 되어 갈 수 있는 길이 된다.
4. 이 과정을 반복하여 갈 수 있는 길을 카운트하여 답을 낸다.

#include <iostream>
using namespace std;

const int MAX = 100;
int N, L, ans;
int Map[MAX][MAX];

void Input() {
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
		}
	}
}
/*
D가 0이라면, 길의 높이가 같은 경우이다.
D가 1이라면, 올라가는 경사로가 필요한 경우이다.
D가 -1이라면, 내려가는 경사로가 필요한 경우이다.
길의 높이가 같다면 (D == 0), 카운트를 1 증가시킨다. 카운트는 경사로의 길이와 비교하기 위해 필요하다.
올라가는 경사로라면 (D == 1), 카운트가 경사로의 길이 L 이상인지 확인한다. 카운트가 L 이상이라면,
경사로를 놓을 수 있는 경우이므로, 카운트를 1로 초기화시킨다.
내려가는 경사로라면 (D == -1), 카운트가 0 이상인지 확인한다. 
0 이상이라면, 카운트를 경사로의 길이 L만큼을 음수로 만든다. 
만약 카운트가 음수라면, 내려가는 경사로를 만들고 있는 중이므로, 경사로를 놓을 수 없다.
*/
void slope(int i, bool c) {
	int cnt = 1;
	for (int j = 0; j < N - 1; j++) {
		//행이냐 열이냐
		int d = c == true ? Map[i][j + 1] - Map[i][j] : Map[j + 1][i] - Map[j][i];
		if (d == 0) cnt++;
		else if (d == 1 && cnt >= L) cnt = 1;
		else if (d == -1 && cnt >= 0) cnt = -L + 1;
		else return;
	}
	if (cnt >= 0) ans += 1;
}
void Process() {
	for (int i = 0; i < N; i++) {
		slope(i, true);
		slope(i, false);
	}
}
void Solution() {
	Input();
	Process();
	cout << ans << "\n";
}
int main() {
	freopen("12.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}