14890 경사로

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

14890번: 경사로

어제 자기 전에 문제를 한 번 봤는데 생각보다 할 만 하지 않을까 라는 생각을 하며 잠에 들고 깨서 풀어보았다. 푸는데 두 시간 정도 걸린 것 같다. 처음에는 가로로 한 번 보고, 세로로 한 번 봐야겠다. 라는 생각을 했는데 그럴 필요 없이 위에서 아래로 내려오면서 검사하는 알고리즘을 짜고, 보드를 회전시키면 따로 작업할 필요가 없다. while문의 조건을 잘못 쓰는 등 실수를 해서 푸는데 시간이 좀 걸렸다. 원래는 while문 대신 for문을 사용했는데 증가식 부분이 걸리적거려서 while문을 사용했다.

#include <bits/stdc++.h>
using namespace std;
int N,L,cnt;
int board[103][103];
bool used[101]; //경사로를 놓은 칸을 표시 

void rotate(){
	int tmp[103][103];
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			tmp[i][j]=board[i][j];
			
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			board[i][j]=tmp[N-1-j][i];
}

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

	for(int rot=0;rot<2;rot++){
		for(int i=0;i<N;i++){ //가로 이동 
			bool cango=true;
			fill(used,used+101,false);
			int j=0;
			while(j<N-1){ //세로 이동 
				int diff=board[j][i]-board[j+1][i];
				if(!diff){j++; continue;} //차이가 없으면 continue
				if(abs(diff)>=2){cango=false; break;} //차이가 2이상이면 놓을 수 없음
				
				if(diff==1){ //내리막이면 
					int standard=board[j+1][i]; 
					for(int k=1;k<=L;k++){ //현재 좌표에서 경사로의 길이만큼 이동 
						if(j+k>=N||board[j+k][i]!=standard||used[j+k]){cango=false; break;};
						used[j+k]=true; 
					}
					if(!cango) break;
					else j=j+L;
				}
				if(diff==-1){ //오르막이면 
					int standard=board[j][i];
					for(int k=0;k<L;k++){
						if(j-k<0||board[j-k][i]!=standard||used[j-k]){cango=false; break;};
						used[j-k]=true;
					}
					if(!cango) break;
					else j++;
				}
			}
			if(cango){cnt++;cout<<i+1<<"줄 ok"<<'\n';}
		}
		rotate();
		cout<<"회전함\n";
	}
	cout<<cnt;
	return 0;                                 
}

 

rotate함수가 오른쪽 회전을 시키므로 rotate 후에 출력되는 줄 번호는 기존 보드의 하단 행부터 시작한다. 코드를 다 짜고 순간 이 부분이 햇갈려서 이게 왜 되는지 모른 채로 제출하고 성공했다.