백준 16957번 체스판 위의 공

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

16957번: 체스판 위의 공

 

 

 

 

 

<접근방법>

접근 방법이 다양한 문제입니다.

저는 그냥 bfs, 우선순위 큐를 활용한 bfs, dp로 풀었습니다.

 

공은 큰 곳에서 작은 곳으로 흐르기 때문에 우선순위 큐를 활용해 풀 수 있습니다.

 

 

 

1 - 2 - 3 - 4

2 - 3 - 4

 

1 -> 4인 공괴 2 -> 4 인 공은 경로가 겹칩니다.

이 경로를 저장해놓고 중복 탐색을 방지하는 dp로 문제를 풀 수 있습니다.

 

<느낀 점>

중복탐색 - dp

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct point {
	int val, y, x;
};

int n, m;
int map[500][500], visit[500][500];
int dy[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dx[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };

struct cmp {
	bool operator()(point a, point b) {
		return a.val < b.val;
	}
};

priority_queue<point, vector<point>, cmp> q;

void bfs() {
	while (!q.empty()) {
		point t = q.top();
		q.pop();

		if (visit[t.y][t.x] == 0) continue;

		int tmp = 987654321;
		int my, mx;
		for (int i = 0; i < 8; i++) {
			int ny = t.y + dy[i];
			int nx = t.x + dx[i];

			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

			if (tmp > map[ny][nx]) {
				tmp = map[ny][nx];
				my = ny;
				mx = nx;
			}
		}
		if (tmp <= map[t.y][t.x]) {
			visit[my][mx] += visit[t.y][t.x];
			visit[t.y][t.x] = 0;
			q.push({map[my][mx], my, mx });
		}
	}
}

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

			q.push({map[i][j], i, j });
			visit[i][j]++;
		}
	}

	bfs();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << visit[i][j] << ' ';
		}
		puts("");
	}

	return 0;
}

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

struct point {
	int y, x;
};

int n, m;
int map[501][501], ans[501][501];
bool visit[501][501];
point cache[501][501];
int dy[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dx[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };

point dfs(int y, int x) {
	point &res = cache[y][x];
	bool &visited = visit[y][x];
	if (visited) return res;
	visited = true;

	//res.y = y; res.x = x;
	res = {y, x};
	int now_val = map[y][x];
	int ty, tx;
	for (int i = 0; i < 8; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

		if (now_val > map[ny][nx]) {
			now_val = map[ny][nx];
			ty = ny;
			tx = nx;
		}
	}
	if (now_val != map[y][x]) return res = dfs(ty, tx);
	return res;
}

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			point t = dfs(i, j);

			ans[t.y][t.x]++;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << ans[i][j] << ' ';
		}
		puts("");
	}


	return 0;
}