🌱 문제
- 길어서 생략.
🌱 풀이
[문제 설명]
2N개의 길을 하나씩 체크한다.
경사가 나올때 낮은지점의 길이가 l미만이면 불가능한 길이다.
경사가 나올때 높이가 1차이가 아니면 불가능한 길이다
경사로갯수는 한좌표당 1개까지가 가능하다.
[풀이방법]
1.먼저 가로방향, 세로방향으로 나누어서 각각의 좌표에서 높이가 같은 좌표가 연속으로 몇갠지를 세어 row[][] col[][] 배열에 저장한다.
2.이제 가로방향, 세로방향 모든 경로를 보면서 지나갈수 있는 길인지 확인한다.
[2번 과정 자세히보기]
2. 가로방향 길 확인하는 과정(세로도 같으니까 생략)
2-1.
현재 좌표의 다음 좌표(오른쪽 좌표)가 같은 높이인지, 경사가 있는지 확인한다.
경사가 없으면 다음 포문으로 넘어간다.
경사가 있을때 높이 차이가 2이상이면 break하고 높이차이가 1일때만 2-2로 넘어간다.
2-2.
(1)다음좌표가 내리막 경사일때,
다음좌표에서 l길이의 경사로를 놓을수 있는지 확인한다.
check배열을 이용하여 내리막 경사의 l만큼 경사로를 놓는다. (놓으면 true)
이때, 놓기전에 놓을수 있는지 확인하고 이미 놓아져있으면 불가능한 경우이므로 break한다.
(3)다음좌표 오르막 경사일때,
현재 좌표에서 l길이만큼 거꾸로 보면서 경사로를 놓을 수 있는지 확인한다.
마찬가지로 check배열일 이용하여 놓을수 있는지 확인하고, 없다면 break한다.
2-3.
그렇게 해서 한 경로의 마지막 지점(각 행의 마지막 열 인덱스)까지 break가 안걸리면 온전한 경로이므로 answer++한다.
세로도 같은 방법으로 해서 총 합친 answer를 출력한다.
[느낀점]
너무 복잡하고 힘들게 푼거 같다.
더 좋은방법이 분명히 있을거같다 .. 다른사람 풀이들을 확인해봐야 겠다
🌱 풀이 및 코드
//14890번: 경사로
/*
입력
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
출력
첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.
*/
/*
[문제 설명]
2N개의 길을 하나씩 체크한다.
경사가 나올때 낮은지점의 길이가 l미만이면 불가능한 길이다.
경사가 나올때 높이가 1차이가 아니면 불가능한 길이다
경사로갯수는 한좌표당 1개까지가 가능하다.
[풀이방법]
1.먼저 가로방향, 세로방향으로 나누어서 각각의 좌표에서 높이가 같은 좌표가 연속으로 몇갠지를 세어 row[][] col[][] 배열에 저장한다.
2.이제 가로방향, 세로방향 모든 경로를 보면서 지나갈수 있는 길인지 확인한다.
[2번 과정 자세히보기]
2. 가로방향 길 확인하는 과정(세로도 같으니까 생략)
2-1.
현재 좌표의 다음 좌표(오른쪽 좌표)가 같은 높이인지, 경사가 있는지 확인한다.
경사가 없으면 다음 포문으로 넘어간다.
경사가 있을때 높이 차이가 2이상이면 break하고 높이차이가 1일때만 2-2로 넘어간다.
2-2.
(1)다음좌표가 내리막 경사일때,
다음좌표에서 l길이의 경사로를 놓을수 있는지 확인한다.
check배열을 이용하여 내리막 경사의 l만큼 경사로를 놓는다. (놓으면 true)
이때, 놓기전에 놓을수 있는지 확인하고 이미 놓아져있으면 불가능한 경우이므로 break한다.
(3)다음좌표 오르막 경사일때,
현재 좌표에서 l길이만큼 거꾸로 보면서 경사로를 놓을 수 있는지 확인한다.
마찬가지로 check배열일 이용하여 놓을수 있는지 확인하고, 없다면 break한다.
2-3.
그렇게 해서 한 경로의 마지막 지점(각 행의 마지막 열 인덱스)까지 break가 안걸리면 온전한 경로이므로 answer++한다.
세로도 같은 방법으로 해서 총 합친 answer를 출력한다.
[느낀점]
너무 복잡하고 힘들게 푼거 같다.
더 좋은방법이 분명히 있을거같다 .. 다른사람 풀이들을 확인해봐야 겠다
*/
#include <iostream>
#include <cstring> //memset사용 위해 선언
using namespace std;
int n,l;
int arr[100][100];
bool check[100][100]; //해당 좌표에 경사로를 놓았는지 여부
int answer;
int row[100][100];
int col[100][100];
const int ROW_MAX=100;
const int COL_MAX=100;
bool flag;
void func(){
//가로 모양경로
//각각의 좌표에서 가로모양으로 같은 높이가 연속하여 몇개인지 row[][]에 저장
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int value=arr[i][j];
int cnt=1;
if(row[i][j]!=0){
continue;
}
if(j==n-1){
row[i][j]=cnt;
continue;
}
for(int k=j+1; k<n; k++){
if(value==arr[i][k]){
cnt++;
}else{
for(int y=j; y<j+cnt; y++){
row[i][y]=cnt;
}
break;
}
for(int y=j; y<j+cnt; y++){
row[i][y]=cnt;
}
}
}
}
//세로 모양경로
//각각의 좌표에서 세로모양으로 같은 높이가 연속하여 몇개인지 col[][]에 저장
for(int j=0; j<n; j++){
for(int i=0; i<n; i++){
int value=arr[i][j];
int cnt=1;
if(col[i][j]!=0){
continue;
}
if(i==n-1){
col[i][j]=cnt;
continue;
}
for(int k=i+1; k<n; k++){
if(value==arr[k][j]){
cnt++;
}else{
for(int x=i; x<i+cnt; x++){
col[x][j]=cnt;
}
break;
}
for(int x=i; x<i+cnt; x++){
col[x][j]=cnt;
}
}
}
}
}
int main(){
cin>>n>>l;
ios::sync_with_stdio(false);
cin.tie(NULL);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>arr[i][j];
}
}
func(); // 같은 높이 연속하는 갯수 저장하는 함수
//가로모양 길 확인
for(int i=0; i<n; i++){
flag=true;
for(int j=0; j<n-1; j++){
if(arr[i][j+1]!=arr[i][j]){ //다음 좌표와 높이 다른경우
int a=abs(arr[i][j+1]-arr[i][j]); //다음 좌표와의 높이 차이
if(a>=2){ //높이차이가 2이상이면 불가능한 길
break;
}else{ //높이차이가 1이면
if(arr[i][j+1]>arr[i][j]){ //오르막인경우, 현재까지의 row값이 2이상이 아니면 경사를 놓을 수 없으므로 break
if(row[i][j]<l){
break;
}
for(int k=j; k>j-l; k--){
if(check[i][k]==true){
flag=false;
break;
}else{
check[i][k]=true;
}
}
}else{ //내리막 인경우, 그다음 좌표의 row값이 l보다 작으면 break;
if(row[i][j+1]<l){
break;
}
for(int k=j+1; k<j+1+l; k++){
if(check[i][k]==true){
flag=false;
break;
}else{
check[i][k]=true;
}
}
}
}
}
if(flag==false){
continue;
}else{
if(j==n-2){ // 가로길의 끝까지 왓으면
answer++;
}
}
}
}
//check배열 초기화
for(int i=0; i<ROW_MAX; i++){
memset(check[i], false, sizeof(check[i]));
}
//세로모양 길 확인
for(int j=0; j<n; j++){
flag=true;
for(int i=0; i<n-1; i++){
if(arr[i+1][j]!=arr[i][j]){ //다음 좌표와 높이 다른경우
int a=abs(arr[i+1][j]-arr[i][j]); //다음 좌표와의 높이 차이
if(a>=2){ //높이차이가 2이상이면 불가능한 길
break;
}else{ //높이차이가 1이면
if(arr[i+1][j]>arr[i][j]){ //오르막인경우, 현재까지의 col값이 2이상이 아니면 경사를 놓을 수 없으므로 break
if(col[i][j]<l){
break;
}
for(int k=i; k>i-l; k--){
if(check[k][j]==true){
flag=false;
break;
}else{
check[k][j]=true;
}
}
}else{ //내리막 인경우, 그다음 좌표의 col값이 l보다 작으면 break;
if(col[i+1][j]<l){
break;
}
for(int k=i+1; k<i+1+l; k++){
if(check[k][j]==true){
flag=false;
break;
}else{
check[k][j]=true;
}
}
}
}
}
if(flag==false){
continue;
}
else{
if(i==n-2){ // 세로길의 끝까지 왓으면
answer++;
}
}
}
}
cout<<answer<<"\n";
}
공부한 내용 잊어버리지 않게 기록하는 공간!