삼성 코딩테스트 기출_(백준)경사로

난이도 ★★☆

 

문제출처

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

14890번: 경사로

포인트

1. 구조 : 행 검사 / 열 검사 / 경사로 설치

(1) 행별로, 지나갈 수 있는 길인지에 대한 여부를 먼저 검사한다 : passableR()

(1-1) 행별로 검사를 하는 중, 높이가 다른 두 칸이 인접한 경우에는 경사로를 설치할 수 있는지를 검사한다.

(1-2) 경사로를 설치할 수 있는 경우, ramp[][] 배열의 초기값 0을 1로 업데이트한다.

(2) 열별로, 지나갈 수 있는 길인지에 대한 여부를 다음으로 검사한다 : passableC()

(2-1) 열별로 검사를 하는 중, 높이가 다른 두 칸이 인접한 경우에는 경사로를 설치할 수 있는지를 검사한다.

(2-2) 경사로를 설치할 수 있는 경우, ramp[][] 배열의 초기값 0을 1로 업데이트한다.

 

2. 행 검사 끝난 뒤, 열 검사 하기 전에 ramp 배열 초기화하기

필자는 행별로 지나갈 수 있는 길인지에 대한 검사(passableR())를 실시한 후, 열별로 지나갈 수 있는 길인지에 대한 검사(passableC())를 실시한다. 그리고 각각의 passable검사를 실시할 때, 경사로를 설치한 경우 ramp[][]에 업데이트를 해준다. 여기에서, 행 검사를 할 때 썼던 ramp[][]을 초기화하지 않은 채 열 검사를 실시하게 되면 당연히 틀린 답 도출

 

정답코드

#include <iostream>
#include<stdlib.h>
using namespace std;
int N, L;
int map[101][101];
int ramp[101][101];

//행 검사
bool passableR(int r) {
	//r행의 첫 번째 칸을 초기값 temp로 저장해놓기
	int temp = map[r][0];
	int diff = 0;
    
    	//r행의 모든 칸 순회
	for (int i = 1; i < N; i++) {
    		//높이가 다른 칸 발견시
		if (map[r][i] != temp) {
        		//높이 차이 구하기
			diff = abs(map[r][i] - temp);
            		//차이가 1이 아닌 경우(1이상인 경우) 무조건 false
			if (diff != 1) return false;
			
            		//더 높은 칸을 만난 경우
			if (map[r][i] > temp) {
				bool flag = true;
                		//이전 L개의 칸이 모두 같은 높이인지(경사로 설치할 수 있는지) 확인
				for (int j = 1; j <= L; j++) {
					if (i - j < 0 || ramp[r][i - j] || map[r][i-j]!=map[r][i]-1) {
						return false;
					}
				}
                		//가능한 경우, 경사로 설치
				if (flag) {
					for (int j = 1; j <= L; j++) {
						ramp[r][i - j] = 1;
					}
				}
                		//temp 값 업데이트
				temp = map[r][i];
			}
            
            		//더 낮은 칸을 만난 경우
			else if (map[r][i] < temp) {
				bool flag = true;
                		//이후 L개의 칸이 모두 같은 높이인지(경사로를 설치할 수 있는지) 확인
				for (int j = 0; j < L; j++) {
					if (i + j >= N || ramp[r][i + j] || map[r][i] != map[r][i + j]) {
						return false;
					}
				}
                		//가능한 경우, 경사로 설치
				if (flag) {
					for (int j = 0; j < L; j++) {
						ramp[r][i+j] = 1;
					}
				}
                		//temp값 업데이트
				temp = map[r][i];
			}
		}
	}
	return true;
}

//열 검사(행 검사와 동일한 방식)
bool passableC(int c) {
	int temp = map[0][c];
	int diff = 0;
	for (int i = 1; i < N; i++) {
		if (map[i][c] != temp) {
			diff = abs(map[i][c] - temp);
			if (diff != 1) return false;

			if (map[i][c] > temp) {
				bool flag = true;
				for (int j = 1; j <= L; j++) {
					if (i - j < 0 || ramp[i-j][c] || map[i - j][c] != map[i][c] - 1) {
						return false;
					}
				}
				if (flag) {
					for (int j = 1; j <= L; j++) {
						ramp[i-j][c] = 1;
					}
				}
				temp = map[i][c];
			}
			else if (map[i][c] < temp) {
				bool flag = true;
				for (int j = 0; j < L; j++) {
					if (i + j >= N || ramp[i + j][c] || map[i][c] != map[i+j][c]) {
						return false;
					}
				}
				if (flag) {
					for (int j = 0; j < L; j++) {
						ramp[i + j][c] = 1;
					}
				}
				temp = map[i][c];
			}
		}
	}
	return true;
}

int main() {
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	int ans = 0;
    
    //행 검사
	for (int i = 0; i < N; i++) {
		if (passableR(i)) ans++;
	}

	//(중요) ramp배열 초기화
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ramp[i][j] = 0;
		}
	}

	//열 검사
	for (int i = 0; i < N; i++) {
		if (passableC(i)) ans++;

	}

	cout << ans << '\n';

	return 0;
}