[C++/25565] 딸기와 토마토

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

단순한 공식을 도출해 문제를 푸는 것인줄 알았지만, 여러가지 조건을 생각해봐야하는 문제였습니다. 진짜 틀렸습니다만 1시간을 달리다가 문제를 풀었습니다. 정답비율을 떨어뜨리는데 일조했습니다.

천천히 보겠습니다. 입력값은 n,m,k가 공백으로 주어지는데 1 <= n,m <= 2000 / 1 <= k <= max(n,m) 입니다. n,m,k는 그닥 입력값이 크지 않기 때문에 입력에는 크게 문제가 없을 것 같습니다.

내용은 이렇습니다. 어쩄든 딸기와 토마토를 가로든 세로든 한줄로 한 보드(n * m)에 심습니다. 그래서 어찌됐든 딸기와 토마토는 어떻게 심게되냐면?

0. 토마토와 딸기 전부 겹치지 않는다. (k * 2)

1. 토마토와 딸기를 한줄에 전부 다 심는 경우(딸기와 토마토가 전부 겹친다.)

2. 토마토와 딸기를 십자가 모양으로 심는 경우 무조건 1개가 겹친다. (한개만 겹친다.)

3. 토마토와 딸기를 한줄에 전부 다 심지만, 딸기 딸기 딸기 (딸기,토마토) 토마토 토마토 토마토 이런식으로 심는다. (1개가 겹칠수도 그리고 k - 1개가 겹친다.)

등등, 여러가지 방식이 많다. 그래서 여러가지 다양한 경우를 따져봐야한다. 코드를 작성할때 여러가지 경우의 수를 다 찾아보고 코드를 작성했어야 했는데, 계속해서 조건을 찾으면서 코딩을 하다보니까 코드가 매우 더러워 졌다.

저는 일단 보드위에 있는 1의 개수를 전부 세었습니다. 1의 개수에 따라서 경우의 수가 달라지기 때문입니다. 하나하나 작성해보겠습니다.

0. 1의 개수가 k * 2 이라면?

토마토와 딸기가 겹쳐진 구간이 없으므로, 0을 출력합니다.

1. 1의 개수가 K * 2 - 1 이라면?

겹쳐지는 구간이 존재합니다. 하지만 이 안에서도 다양한 조건이 존재합니다.

- k가 1이라면? 물론 1개가 존재하기 때문에 1의 위치가 겹쳐진 구간입니다.

- 처음으로 발견된 1에서 4방향을 전부 살펴보는데, 그 위치에서 2개 이상의 1이 존재한다면? 시작부터 겹쳐지는 구간입니다.

- 그런것이 발견되지 않고, 이어나갈때, 이전 이동방향말고 전환되는 부분이 있다면? 그 부분이 겹치는 점입니다.

- 위의 경우에 전부 해당하지 않는다면? 가로든 세로든 이어지면서 토마토와 딸기가 심어졌고, 한개의 겹치는 위치가 존재합니다. 

2. 전체가 전부 겹쳐졌을때 findFruit()

3. 그외 나머지, 일자(가로,세로)로 겹쳐졌을 때, 몇개가 겹쳐졌는지 확인하는 방법

여기에는 공식이 하나 있습니다. 토마토와 딸기의 총 개수 (k * 2) 에서 보드에 주어진 1의 개수를 빼면 겹쳐진 값이 나옵니다.

그리고 전체 길이에서 겹쳐진 과일의 개수를 빼고 2로 나누게 된다면? 앞 뒤로 해당 값만큼 이동한 곳부터 겹쳐진 토마토와 딸기가 나오게 됩니다. 이 방식으로 문제를 해결할 수 있고, 그리고 가로인지 세로인지 파악하는 코드를 작성한 후 문제를 해결했습니다. 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>

#define MAX 2010
using namespace std;

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

int cnt = 0,n,m,k,board[MAX][MAX];
vector<pair<int,int> > v;

struct info{
	
	int y;
	int x;
	int dir;
	
};

int visited[MAX][MAX];
queue<info> q;

void init() {
	
	cin >> n >> m >> k;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
			if(board[i][j]) cnt++;
		}
	}

}

int isRange(int y, int x){
	return 0 <= y && y < n && 0 <= x && x < m;
}

bool cmp(pair<int,int> &a, pair<int,int> &b){
	if(a.first == b.first){
		return a.second < b.second;
	}
	return a.first < b.first;
}

void intersection(int y, int x){
	
	memset(visited,0,sizeof(visited));
	
	// 1 0 0 
	// 0 0 0
	// 0 0 0
	if(k == 1){
		v.push_back({y,x});
		return;
	}
	
	int origin_y = y; int origin_x = x;
	visited[y][x] = 1;
	
	int cnt = 0;
	for(int i = 0; i < 4; i++){
		
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(isRange(ny,nx) && board[ny][nx]){
			visited[ny][nx] = 1;
			q.push({ny,nx,i});
			cnt++;
		}
		
	}
	
	// 1 1 1
	// 1 0 0
	// 1 0 0
	if(cnt >= 2){
		v.push_back({y,x});
		return;
	}
	
	while(!q.empty()) {
		
		int y = q.front().y;
		int x = q.front().x;
		int dir = q.front().dir;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(!isRange(ny,nx)) continue;
			if(!board[ny][nx]) continue;
			if(visited[ny][nx]) continue;
			
			if(dir != i){
				v.push_back({y,x});
				return;
			}
			
			visited[ny][nx] = 1;
			q.push({ny,nx,i});
		}
	}
	
	// k = 2, n = 3 m = 3 
	// 1 1 1
	// 0 0 0
	// 0 0 0
	
	if(!v.size()){
		
		int y = origin_y;
		int x = origin_x;
		
		// down
		for(int i = 0; i < k - 1; i++){
			y += dy[0];
			x += dx[0];
		}
		
		if(board[y][x] == 1){
			v.push_back({y,x});
		}
		 
		y = origin_y;
		x = origin_x;
		
		// right
		for(int i = 0; i < k - 1; i++){
			y += dy[2];
			x += dx[2];
		}
		
		if(board[y][x] == 1){
			v.push_back({y,x});
		}
	}
	
}

void findIntersection() {
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(board[i][j]){
				intersection(i,j);
				return;
			}
		}
	}
	
}

void findFruit() {
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(board[i][j]) v.push_back({i,j});
		}
	}

}

pair<int,int> findFruit2() {
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(board[i][j]) return {i,j};
		}
	}
	
}

void solve() {
	
	if(cnt == (k * 2)){ // 전체가 겹치지 않는다.
		return;
	} else if(cnt == (k * 2) - 1){ // 한개만 겹친다.
		findIntersection();
	} else if(cnt == (k * 2) - k){ // 전체가 겹친다.
		findFruit();
	} else{ // 그외의 경우

		int haveFruit = (k * 2) - cnt;
		int all_range = cnt;
		int start = (all_range - haveFruit) / 2;

		pair<int,int> temp = findFruit2();
		
		int y = temp.first;
		int x = temp.second; // (0,0)

		// down
		int down_y = y + dy[0];
		int down_x = x + dx[0];
		//right
		int right_y = y + dy[2];
		int right_x = x + dx[2];
		
		if(board[down_y][down_x] == 1){
			
			for(int i = y + start; i < y + start + haveFruit; i++){
				v.push_back({i,x});
			}
			
		} else if(board[right_y][right_x] == 1){

			for(int i = x + start; i < x + start + haveFruit; i++){
				v.push_back({y,i});
			}
			
		}
		
	}
	
	if(v.size()) sort(v.begin(), v.end(), cmp);
	
}

int main() {
	
	init();
	solve();
	
	cout << v.size() << "\n";
	for(int i = 0; i < v.size(); i++){
		cout << v[i].first + 1 << " " << v[i].second + 1 << "\n";	
	}
	
	return 0;
}