- 문제를 보고 해결 방법을 떠올리지 못하였고, 문제 분류를 보고도 떠올리지 못하였다.ㅠㅠ
- 기본 bfs => 시간 초과
- 배열의 각 수가 0~200 임을 알고 이분탐색과 bfs를 이용한다.
- 최고 큰수, 작은수 저장하여 반토막을 내고 갈 수 있는지 없는지 bfs를 확인하여 체크
- 최소값과 최대값을 다 체크하면서 bfs를 해야한다.
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct node {
int diff;
int mininum;
int maxinum;
};
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
priority_queue<pii,vector<pii>, greater<pii> > q;
int n, map[110][110];
node dist[110][110];
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < n; j++) {
scanf("%d", &map[i][j]);
dist[i][j].diff = 1e9;
}
}
dist[0][0].diff = 0;
dist[0][0].mininum = dist[0][0].maxinum = map[0][0];
q.push({ 0,{0, 0} });
while (!q.empty()) {
pii now = q.top();
if (now.second.first == n - 1 && now.second.second == n - 1) {
printf("%d", now.first);
break;
}
q.pop();
for (int i = 0; i < 4; i++) {
int nr = now.second.first + dx[i], nc = now.second.second + dy[i];
if (0 <= nr && nr <= n && 0 <= nc && nc <= n) {
int tmp_max = dist[now.second.first][now.second.second].maxinum;
int tmp_min = dist[now.second.first][now.second.second].mininum;
if (tmp_max < map[nr][nc]) tmp_max = map[nr][nc];
if (tmp_min > map[nr][nc]) tmp_min = map[nr][nc];
if (dist[nr][nc].diff > tmp_max - tmp_min) {
q.push({ tmp_max - tmp_min,{nr, nc} });
dist[nr][nc].diff = tmp_max - tmp_min;
dist[nr][nc].maxinum = tmp_max;
dist[nr][nc].mininum = tmp_min;
}
}
}
}
}
