백준 14890 경사로

문제 : https://www.acmicpc.net/problem/14890

 

서론

정말 오래 걸린 문제. 3시간 넘게 푼것 같다.

시뮬레이션 문제라서 문제에서 시킨대로 풀면 된다.

버그 하나 뜨면 반복문과 조건문이 정말 많은데 중간에 나눌 수 있는 부분들도 아니라서 마치 엉킨 실타래 푸는 느낌이었다.

 

---

풀이

지도의 모든 열과 행을 조사해서 통과하는지 확인시켜주면 된다.

아래의 코드는 단 하나의 행이나 열이 통과하는지 확인하는 코드다. 

이 코드에서 반복문이 얼마나 반복해야할지, 배열 인덱스의 정확한 위치 등 많은 조정이 필요하다. 이부분이 상당히 오래걸린다.

void 확인(){
    for(int i=0;i<n;i++){
    	int visited[n]; // 사다리 중복 체크
    	if(map[i] == map[i+1]) continue; // 이동할 칸이 현재칸과 같으면 한칸 이동
        else if (map[i] == map[i+1] -1){ // 이동할 칸이 현재칸보다 1 크면
        	while(cnt++ < l){
            	if(visited[i - cnt] == 0 && map[i] != map[i - cnt]) return; // 사다리를 놓을 수 없으면 진행불가
                else visited[i - cnt] = 1 // 사다리를 중복해서 놓을 수 없게 함
            }
        }
        else if (map[i] == map[i+1]+1){ // 이동할 칸이 현재칸보다 1 작으면 
        	while(cnt++ < l){
            	if(visited[i + cnt] == 0 && map[i] != map[i + cnt]) return; // 사다리를 놓을 수 없으면 진행불가
                else visited[i - cnt] = 1 // 사다리를 중복해서 놓을 수 없게 함
            }
            i += l // 사다리 놓은 만큼 이동
        }
        else return; // 현재칸보다 이동할 칸이 아주 크거나 작거나 한 경우이므로 탈출
    }
}

 

---

구현

// c++

#include <iostream>

using namespace std;

int map[100][100];
int n, l;

void init() {
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
}

int main() {
	init();

	int sum = 0;
	// 행, 우측
	for (int i = 0; i < n; i++) {
		bool flag = true;
		int visited[100] = { 0, };
		for (int j = 0; j < n - 1; j++) {
			if (map[i][j] == map[i][j + 1]) continue;
			else if (map[i][j] == map[i][j + 1] - 1) { // 오르막길
				int cnt = -1;
				while (cnt++ < l - 1) { 
					if (j - cnt < 0 || visited[j - cnt] == 1 || map[i][j] != map[i][j - cnt]) {
						flag = false;
						break;
					}
					else visited[j - cnt] = 1;
				}
			}
			else if (map[i][j] == map[i][j + 1] + 1) { // 내리막길
				int cnt = 0;
				while (cnt++ < l) {
					if (j + cnt >= n || visited[j + cnt] == 1 || map[i][j + 1] != map[i][j + cnt]) {
						flag = false;
						break;
					}
					else visited[j + cnt] = 1;
				}
				if (flag == true) { 
					j += l - 1; 
					continue;
				}
			}
			else {
				flag = false;
				break;
			}
		}
		if (flag == true) { 
			//cout << "행 : " << i << endl;
			sum++; 
		}
	}

	// 열, 아래
	for (int i = 0; i < n; i++) {
		bool flag = true;
		int visited[100] = { 0, };
		for (int j = 0; j < n - 1; j++) {
			if (map[j][i] == map[j + 1][i]) continue;
			else if (map[j][i] == map[j + 1][i] - 1) { // 오르막길
				int cnt = -1;
				while (cnt++ < l - 1) {
					if (j - cnt < 0 || visited[j - cnt] == 1 || map[j][i] != map[j - cnt][i]) {
						flag = false;
						break;
					}
					else visited[j - cnt] = 1;
				}
			}
			else if (map[j][i] == map[j + 1][i] + 1) { // 내리막길
				int cnt = 0;
				while (cnt++ < l) {
					if (j + cnt >= n || visited[j + cnt] == 1 || map[j + 1][i] != map[j + cnt][i]) {
						flag = false;
						break;
					}
					else visited[j + cnt] = 1;
				}
				if (flag == true) {
					j += l - 1;
					continue;
				}
			}
			else {
				flag = false;
				break;
			}
		}
		if (flag == true) {
			//cout << "열 : " << i << endl;
			sum++;
		}
	}

	cout << sum;
}