[구름톤 챌린지] 구름 찾기 깃발

구름 찾기 깃발

dfs/bfs같은 알고리즘을 사용할 필요도 없이 각 좌표의 상하좌우 8칸을 모두 검사해주면 되는 간단한 문제였다.

좌표평면에서 상하좌우를 연산하는 방법은 배열을 만들어주면 쉬운데, 나같은 경우는 dx,dy라는 배열을 만들어서 현재좌표에 더해주는 값으로 사용했다.

int dx[8]={0,0,1,-1,-1,1,1,-1};
int dy[8]={1,-1,0,0,1,1,-1,-1};

여기서 map의 범위 내이고, 더한 좌표에 깃발이 존재한다면 원래 좌표와 같은 위치의 tmp배열에 1을 증가시켰다.

n의 최대값이 1000이므로 이차원배열을 가정했을 때 1000*1000으로 1000000의 크기만큼 연산을 반복하는데, 각 좌표마다 최대 8번 반복하므로 8000000회 연산한다.

map[i][j]가 1일 때는 8회 연산을 하지 않고 스킵하므로 실제 연산의 수는 이보다 적을 것이다.

이런 문제는 푸는 방법이 정해져있어서 비교적 간단하게 풀었다.

#include <iostream>
using namespace std;

int dx[8]={0,0,1,-1,-1,1,1,-1};
int dy[8]={1,-1,0,0,1,1,-1,-1};

int main() {
	int map[1001][1001];
	int tmp[1001][1001];
	
	int n,k,ans=0;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			tmp[i][j]=0;
			cin>>map[i][j];
			if (map[i][j]==1)
				tmp[i][j]=-1;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if (map[i][j]==1)
				continue;
			for(int k=0;k<8;k++){
				int x=dx[k]+j;
				int y=dy[k]+i;
				if ((x>=0&&x<n)&&(y>=0&&y<n)){
					if (map[y][x]==1){
						tmp[i][j]++;
					}
				}
			}
			if (tmp[i][j]==k)
				ans++;
		}
	}
	// cout<<'\n';
	// for(int i=0;i<n;i++){
	// 	for(int j=0;j<n;j++)
	// 		cout<<tmp[i][j]<<" ";
	// 	cout<<"\n";
	// }
	
	cout<<ans;
	return 0;
}

여담

이 문제보다 6회차 문자열 나누기 문제가 더 어려웠는데, 블로그에 남기기엔 부족하다고 생각해서 넘겼다. 문제가 해석하기 어렵게 써져있었다.
사람들도 풀이보고 화났는지 문제가 싫어요 테러를 당했다. 나도 누름

열심히 연산해서 내가 생각하기에 맞는 횟수가 나왔는데도 자꾸 틀려서 풀이를 확인했더니 문제에서 설명을 모호하게 한 부분이 함정이었다. ㅡㅡ

그래도 6회차 문제 계기로 수학공부 해야겠다고 다짐하고 문제집도 구매했으니 새로운 도전을 하게해준 셈 치기로 함