백준 알고리즘 14890_경사로 C

문제

(링크) 14890번: 경사로 (acmicpc.net)

14890번: 경사로

 

사고과정

처음 문제를 봤을 때, 조금 복잡하다고 생각했다. 문제 길이도 길 뿐더러 처리해야할 조건이 각 줄에서 초기화 되어야하기 때문이다. 그리고 독해력이 딸린건지 문제조건이 잘 안들어오기도 했다. 제일 헷갈렸던 점은, 각 보행로를 만들 때 사용한 경사로는 다시 제거가 되는건지, 교차지점에서 영향을 주는건지가 였다. 이 것은 예시 입력 아래에 있는 힌트를 보면 각 보행로를 만들 때만 존재하는 경사로라는 것을 알 수 있다.

위 문제가 해결되니 어떻게 문제를 풀어야하는지 감이 왔다. 각 줄에서 경사로를 만든 곳인지 판별하는 배열과 해당 줄이 보행로로 적합한 곳인지 판별하는 함수, 이 2개가 풀이의 핵심이다. 그런데, 하나의 함수로 2 부분(가로, 세로)을 탐색하고자 하니, 전체 정보를 담고있는 2차원 배열로는 일반화를 할 수 없어서, temp배열에 각 줄을 복사하여 한 줄씩 탐색하였다.

 

내코드

#include <stdio.h>
#include <stdlib.h>

int map[100][100];
int N, L;

void clear(int* build) {
	for (int i = 0; i < N; i++) {
		build[i] = 0;
	}
}

int isPossible(int*temp,int* build) {
	int end_flag = 0;
	for (int i = 0; i < N - 1; i++) {
		int a = temp[i];

		if (a == temp[i + 1])continue;
		else if (a != temp[i + 1]) {
			if (a - temp[i + 1] == 1) {
				if (i + L < N) {
					for (int j = i + 1; j < i + 1 + L; j++) {
						if (temp[j] == temp[i + 1]) {
							build[j] = 1;
						}
						else {
							end_flag = 1;
							break;
						}
					}
				}
				else end_flag = 1;
			}
			else if (a - temp[i + 1] == -1) {
				if (i - L + 1 >= 0) {
					for (int j = i; j > i - L; j--) {
						if (build[j] == 1 || temp[j] != temp[i]) {
							end_flag = 1;
							break;
						}
						else continue;
					}
				}
				else end_flag = 1;
			}
			else end_flag = 1;
		}

		if (end_flag)break;
	}
	return !end_flag;
}



int main() {
	int i,j;
	scanf_s("%d %d", &N, &L);
	int* build = (int*)calloc(N, sizeof(int));
	int* temp = (int*)malloc(N * sizeof(int));
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf_s("%d", &map[i][j]);
		}
	}



	int answer = 0;
	//row 
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			temp[j] = map[i][j];
		}
		if (isPossible(temp, build))answer++;
		clear(build);
	}


	//col 
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			temp[j] = map[j][i];
		}
		if (isPossible(temp, build)) answer++;		
		clear(build);
	}

	printf("%d", answer);

	free(build);
	free(temp);
	return 0;
}

먼저 temp와 build 배열은 map을 한 줄씩 탐색할 것이기 때문에, 각 줄의 정보(높이,경사)를 저장하는 역할을 한다. 각 줄의 탐색이 끝나고 모두 초기화를 해줘야 오류없이 코드가 돌아간다. 그래서 clear함수를 이용해 (경사로 건설여부정보를 담고있는) build를 0으로 초기화 한다.

isPossible함수에선 temp와 build를 인자로 받아, 각 줄의 시작점부터 마지막 전 점까지(N-2)탐색을 시작한다. 시작점은 가로방향은 왼쪽 (map[i][0]) 세로방향은 위 (map[0][i])이다.

방법은 간단하다. 현재지점과 다음지점의 높이를 비교한다. 만약 둘의 높이가 같다면, continue, 같지않다면 그 높이차를 계산한다.  높이차가 1이 아니면 해당 함수를  끝내고, 높이차가 1인 경우 높아졌는지 낮아졌는지를 구한다. 높이가 높아진다면 그 지점으로부터 L번 경사로를 지을 수 있는지 탐색한다. 높이에 변화가 있어 경사로를 지을 수 없다면 코드를 끝내고 경사로를 지을 수 있으면 해당지점의 build배열을 1로 갱신한다. 높이가 낮아진다면, 현재 지점으로부터 L번 지나온길을 검사한다. 만약 경사로를 지을 수 없는 조건(이미 경사로가 만들어졌거나 높이가 다른경우)이 있다면 함수를 끝낸다. 

이후 main에서 answer을 갱신하며 줄을 바꿔준다.

 

피드백

쓸데없이 temp배열에 옮겨온 감이 있다. 해당 부분을 고치면 메모리를 줄일 수 있을 것이다.