백준 2452 그리드 게임 (c++) : 피너클

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

2452번: 그리드 게임

bfs를 이용한 어려운 문제다.

bfs를 활용하는데 있어 어려움을 겪다가 https://jjaewon.tistory.com/7 블로그를 보고 힌트를 얻었다.

cin >> n >> m;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> arr[i][j];
	}
}

입력을 받은다음

memset(visited, false, sizeof(visited));
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (!visited[i][j]) {
			v.push_back({ i, j });
			chk(i, j);
		}
	}
}

visited배열을 false로 초기화하고 vector<pair<int, int>> v를 선언한다.

그후 입력받은 배열을 돌며 방문하지 않은 배열이라면 v안에 배열을 넣고 chk함수를 돌린다.

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

void chk(int y, int x) {
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (0 <= ny && ny < n && 0 <= nx && nx < m) {
			if(!visited[ny][nx] && arr[y][x] == arr[ny][nx]) chk(ny, nx);
		}
	}
}

chk함수는 자신과 같은 색의 돌들을 방문한것으로 표시하는 함수다.

위와같이 돌들이 있다고 했을때 (0, 0) 돌을 기준으로 바꾸면

다음과 같이 바뀌고 (0, 1) 돌을 기준으로 바꿔도

다음과 같이 바뀐다. 굳이 모든 돌을 확인할 필요 없이 각 구역마다 한개씩만 확인하면 된다.

int ans = 987654321;
for (int i = 0; i < v.size(); i++) {
	memset(dist, 10001, sizeof(dist));
	dist[v[i].first][v[i].second] = 0;
	ans = min(ans, bfs(v[i].first, v[i].second));
}
cout << ans << endl;

그후 v안에 있는 배열들을 bfs에 넣고 돌려 그중 가장 작은 값을 ans에 넣어주면 된다.

여기서 bfs가 굉장히 까다로웠다.

int bfs(int a, int b) {
	deque<pair<int, int>> q;
	q.push_back({ a, b } );
	dist[a][b] = 0;
	int ans = -1;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop_front();

이 bfs에서는 deque를 사용한다. deque는 queue와 stack을 합친거라 생각하면 편하다.

앞으로도 넣을수 있고 뒤로도 넣을수 있다. 또 앞의 값을 뺄수도 있고 뒤의 값을 뺄수도 있다.

q에 전달받은 값을 넣고 dist[a][b]를 0으로 바꾼다. dist를 사용하는 이유는 뒤에 나온다.

그후 ans = -1로 초기화 한다음 bfs를 시작한다.

int y에는 q.front().first를, int x에는 q.front().second를 넣고 q의 앞을 pop한다.

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

for문을 돌려 ny값과 nx값을 구한다. ny와 nx는 현재 좌표에서 갈수있는 다음 좌표다.

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				int weight = 0; 
				if (arr[ny][nx] != arr[y][x]) weight = 1;
				if (dist[ny][nx] > dist[y][x] + weight) {
					dist[ny][nx] = dist[y][x] + weight;
					ans = max(ans, dist[ny][nx]);

					if (weight) q.push_back({ ny, nx });
					else q.push_front({ ny,nx });
				}
			}

ny와 nx가 범위 안의 값인지를 확인해주고 범위 안의 값이면

int weight를 선언한다. weight는 현재 좌표에서 다음 좌표로 가는데 드는 비용이다.

만약 현재 좌표와 다음 좌표의 색이 다르다면 weight를 1로 바꾼다.

만약 dist[ny][nx] 가 dist[y][x] + weight보다 크다면, 즉 현재 값에서 다음 값으로 가는 더 비용이 작은 방법이 있다면

dist[ny][nx] 에 dist[y][x] + weight를 넣어주고

ans값을 max(ans, dist[ny][nx]값으로 업데이트해준다.

 

만약 weight가 1이라면, q의 뒤에 ny와 nx값을 넣고 0이라면 앞에 ny와 nx값을 넣는다.

위의 배열에서 (0, 0)에서 (1, 1)로 간다고 하자.

(0, 0) -> (0, 1) -> (1, 1)의 방법이 있을 것이고 (0, 0) -> (1, 0) -> (1, 1)의 방법이 있을 것이다.

위의 bfs는 현재 좌표에서 가장 멀리 있는 좌표를 구하는것이 목표인 함수다.

하지만 그와 동시에 가장 멀리 있는 좌표로 가는 가장 효율적인 방법을 골라야 한다.

잘못하면 위와 같은 상황에서 2번째 방법이 아닌 1번째 방법으로 이동해서 거리가 뻥튀기 되는 참사가 벌여질수있다.

그래서 현재와 같은 색으로 이동하는 좌표를 앞으로 넣어 먼저 검사하고

현재와 다른 색으로 이동하는 좌표는 뒤로 넣어 나중에 검사하는것이다.

현재 색에서 이동할수있는 모든 좌표를 이동한다음 다른 색으로 이동함으로서 효율적인 방법을 찾는것이다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <deque>

using namespace std;

int n, m;
int arr[100][100];
bool visited[100][100];
int dist[100][100];

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

void chk(int y, int x) {
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (0 <= ny && ny < n && 0 <= nx && nx < m) {
			if(!visited[ny][nx] && arr[y][x] == arr[ny][nx]) chk(ny, nx);
		}
	}
}


int bfs(int a, int b) {
	deque<pair<int, int>> q;
	q.push_back({ a, b } );
	dist[a][b] = 0;
	int ans = -1;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop_front();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (0 <= ny && ny < n && 0 <= nx && nx < m) {
				int weight = 0; 
				if (arr[ny][nx] != arr[y][x]) weight = 1;
				if (dist[ny][nx] > dist[y][x] + weight) {
					dist[ny][nx] = dist[y][x] + weight;
					ans = max(ans, dist[ny][nx]);

					if (weight) q.push_back({ ny, nx });
					else q.push_front({ ny,nx });
				}
			}
		}
	}
	return ans;
}

int main()
{
	int a = 0;
	if (a) cout << 1 << endl;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	memset(visited, false, sizeof(visited));
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				v.push_back({ i, j });
				chk(i, j);
			}
		}
	}

	int ans = 987654321;
	for (int i = 0; i < v.size(); i++) {
		memset(dist, 10001, sizeof(dist));
		dist[v[i].first][v[i].second] = 0;
		ans = min(ans, bfs(v[i].first, v[i].second));
	}
	cout << ans << endl;
}

전체코드다.