[BaekJoon] 14890 - 경사로

문제

안녕하세요.
백준에서 삼성 SW 역량 테스트 기출 문제집에 게시된 14890번 경사로 문제 풀이를 소개하겠습니다.

이번 문제는 많은 문제에서 빈번하게 다루는 2차원 배열을 가지고 길을 찾는 문제입니다. 여러 갈래로 나뉜 길의 방향을 찾는 것은 아니고 주어진 길이 이동 가능한지 체크를 하는 문제 입니다. 따라서 조건 처리를 잘 하면 풀 수 있는 문제입니다.

먼저 문제를 정리하면 아래와 같습니다.

주어진 정보

• N x N 배열 : 지도를 의미
• 배열 요소 값 : 지도 위치에 해당하는 땅 높이(층)
• L : 층을 잇는 경사로의 길이

해결 방향

크게 두 단계로 나누도록 하겠습니다.
첫 번째로 가로방향의 길을 전부 확인 후, 두 번째에는 세로 방향의 길을 전부 찾습니다.

2차원 배열에서는 가로-세로의 방향이 있지만, 어느 방향의 길이든 선택하고나면 1차원 배열로 모양이 같아집니다. 이러한 점을 이용하여 하나의 함수를 작성해 모든 방향의 길을 확인할 수 있습니다.

아래는 경사로의 예시와, 2차원 배열에서 이동 가능한 길을 파란색 점선 박스로 표시한 예시 입니다.

경사로 예시

색으로 구분된 이동 가능한 길과 불가능한 길

풀이

풀이 코드

int N, L;
vector < vector<int> > map;

bool run_road(vector<int> road) {
	int i = 1;					// 위치
	int len_flat = 1;			// 지나온 평평한 길 길이
	int cur_h = road.front();	// 현재 땅 높이

	while (true) {
		if (i >= N) break;
		if (abs(cur_h - road[i]) > 1) return false;
		if (cur_h < road[i]) {
			// 올라가는 경우
			// 지나온 땅의 평평한 길이가 L보다 작으면 경사로 설치 불가
			if (len_flat < L) return false;
			cur_h = road[i];
			len_flat = 1;
			i++;
		}
		else if (cur_h > road[i]) {
			// 내려가는 경우
			len_flat = 1;
			cur_h = road[i];
			while (len_flat < L) {
				i++;
				len_flat++;

				if (i >= N) return false;
				if (cur_h != road[i]) return false;
			}
			i++;
			len_flat = 0;
		}
		else {
			// 평평한 길 지나는 경우
			len_flat++;
			i++;
		}
	}

	return true;
}

int solution() {
	int count = 0;

	for (int c = 0; c < N; c++) {
		if (run_road(map[c])) count++;
	}

	for (int r = 0; r < N; r++) {
		vector< int> tmp_road;
		for (int c = 0; c < N; c++)
			tmp_road.push_back(map[c][r]);
		if (run_road(tmp_road)) count++;
	}

	return count;
}

int main() {
	cin >> N >> L;
	map = vector < vector<int> >(N, vector<int>(N));
	
	for (int c = 0; c < N; c++) {
		for (int r = 0; r < N; r++) {
			cin >> map[c][r];
		}
	}

	cout << solution();
	return 0;
}

해설

• solution() : 가로, 세로 각 방향 길들을 전부 확인
• run_road() : 주어진 길을 한칸씩 이동하면서 끝에 도달할 수 있는지 확인
  • 1칸 차이의 높,낮은 칸을 연결
  • L 길이 만큼 공간에 경사로 설치
  • 경우의 수
    1. 높은 칸 만나는 경우
       • 지나온 평지의 길이가 L 이상인 경우
    2. 낮은 칸 만나는 경우
       • 일단 설치하고 한칸씩 전진
       • L만큼 전진하지 못한다면 이동 불가능한 길
    3. 평평한 땅 경우
       • 그냥 이동
         
         

앗 이걸 생각 못했네?

• 경사로를 놓는 수의 제한은 없다.
• 경사로를 내려오고 바로 경사로가 또 이어질 수도 있다.