[백준 14890] 경사로

문제 링크 => 14890번: 경사로 (acmicpc.net)

14890번: 경사로

---

삼성 SW 역량 테스트 문제로 구현 문제이다.

 

경사로를 놓는 방법은 다음과 같이 정리할 수 있다.

 

1. 현재 위치가 x 일 때 다음 위치가 (x + 1) 인 경우 => 현재 위치를 기준으로 L 번 뒤로 이동하면서 경사로를 놓을 수 있는지 체크한다.

 

2. 현재 위치가 x 일 때 다음 위치가 (x - 1) 인 경우 => 다음 위치를 기준으로 L 번 앞으로 이동하면서 경사로를 놓을 수 있는지 체크한다.

 

이때, 1번과 2번을 확인하는 과정에서 예외 케이스로 세가지가 존재한다.

 

(1) 지도의 범위를 벗어나는 경우 ( 0 ~ N-1 내에 존재하지 않을 경우 )

(2) 뒤로 이동한 위치가 x 가 아닌 경우 ( 2차원 배열 Map 에 해당 위치의 값을 확인 )

(3) 해당 위치에 이미 경사로를 놓은 경우 ( 2차원 배열 Ramp 를 사용하여 처리 )

 

또한, 현재 위치값과 다음 위치값의 차이가 2 이상인 경우 또한 처리해줘야 한다.

 

윗 과정이 지도 내에서 시작 지점에서 끝 지점까지 완벽하게 수행된 경우 counting 해준다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, L;
int Map[100][100], Ramp[100][100];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void input() {

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

void ramp_Init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			Ramp[i][j] = 0;
		}
	}
}

int bfs(int start, int direction) {
	queue<pair<int, int>> Q;
	if (direction == 0) Q.push({ start,0 });
	else Q.push({ 0,start });

	while (!Q.empty()) {
		int x = Q.front().first, y = Q.front().second;
		Q.pop();

		int nextX = x + dx[direction], nextY = y + dy[direction];
		if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
			if (Map[nextX][nextY] == Map[x][y]) Q.push({ nextX,nextY });
			else if (abs(Map[nextX][nextY] - Map[x][y]) == 1) {
				// UpRamp
				if (Map[nextX][nextY] > Map[x][y]) {
					int reverseD = direction + 2, cnt = L, cur = Map[x][y];
					while (cnt--) {
						if (x < 0 || x >= N || y < 0 || y>= N ||
							Map[x][y] != cur || Ramp[x][y]) return 0;
						Ramp[x][y] = 1;
						x += dx[reverseD], y += dy[reverseD];
					}
					Q.push({ nextX,nextY });
				}
				// DownRamp
				else {
					int cnt = L, cur = Map[nextX][nextY];
					while (cnt--) {
						x += dx[direction], y += dy[direction];
						if (x < 0 || x >= N || y < 0 || y >= N ||
							Map[x][y] != cur || Ramp[x][y]) return 0;
						Ramp[x][y] = 1;
					}
					Q.push({ x,y });
				}
			}
			else return 0;
		}
	}
	return 1;
}

void solve() {

	int result = 0;
	
	// Right
	for (int i = 0; i < N; i++) {
		ramp_Init();
		result += bfs(i, 0);
	}

	// Down
	for (int i = 0; i < N; i++) {
		ramp_Init();
		result += bfs(i, 1);
	}

	cout << result << endl;

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}