1. 기본 dfs 하면 시간초과가 납니다. 2. 그러므로 다른 방법을 찾아야 하는데, 배열의 각 수가 0~200 사이라는 사실을 알아채고 이분탐색과 bfs 를 사용합니다. 3. 방법은 먼저 배열 내에 가장 작은 수와, 가장 큰수를 찾습니다. 이것을 이분 탐색하면서 범위를 줄여 나가도록 합니다. 예제를 통해서 보면 0~8 을 잘른 4로 시작합니다. 그런데 여기서 큰 for 문 하나를 작성해야 하는데, 이는 가장 작은 수부터, 왜 가장 큰 수까지 조사를 하는 것이지? 가장 작은 수부터, 가장 큰수 - 범위 만큼 l 이 1씩 증가합니다. 이 엘 변수를 사용해서 맵을 구성해줍니다. 갈 수 있는 길과 갈 수 없는 길을 구분합니다. 그리고 bfs 를 통해서 정리된 맵에서 0을 따라서 끝까지 갈 수 있는지 없는지를 판단하면 됩니다. 이분 탐색을 위해서는 변수가 3개 필요합니다. 그리고 end = mid - 1 start = mid + 1 을 하는데 어떤 조건을 갖는지, 그리고 어떻게 사용할 것인지가 분명해야 합니다. 값을 찾기 위해서는 index 도 필요합니다. |
/* 1. 최고 큰 수, 작은 수 저장해서 반토막을 내고, 갈 수 있는지 체크, 갈 수 있으면, 반 토막을 또 내고 갈 수 있는지 체크, 갈 수 없다면, 다시 돌아와서 체크 합니다. 2. 체크 할 때는 bfs 를 사용하면 됩니다. 문제를 정독하고, 그곳에서 힌트를 얻어야 합니다. 여기서는 배열의 각 수는 0보다 크거나, 200보다 작거나 같은 수라는 점입니다. 사실 30분 내로 설계 못하면 못 푼다고 생각하면 됩니다. 0~4 사이로 지나 갈 수 있는가? 이게 아니라 그 경로의 최소와 최대 차이가 4 이내로 지나 갈 수 있는가? 이것을 체크해야 합니다. */ #include <iostream> #include <queue> using namespace std; #define SIZE 105 // 105 struct point { int x, y; }; queue<point> que; int n; int minVal = 2123456789; int maxVal; int ans; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int head, tail, mid; int diff; int x, y, nx, ny; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int range_st, range_ed; void problemIn() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; if (map[i][j] > maxVal) maxVal = map[i][j]; if (map[i][j] < minVal) minVal = map[i][j]; } } } /* 에버리지를 잘 정해야 할 것 같은데, 예를 들어서 4차이 나도록 갈 수 있는지? 확인하려면 어떻게 해야 하나요? */ void init() { // minVal = 2123456789; // maxVal = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { visit[i][j] = 0; } } while (!que.empty()) que.pop(); } /* 내가 원하는 코드는 0 8 오케이 0 4 오케이 0 2 오케이 0 1 안됩니다. 이렇게 하고 끝나는 것을 원합니다. */ int bfs(int mid) { for (int l = minVal; l <= maxVal - mid; l++) { // 갈 수 있는 길 없는 길 구분, 갈 수 있는 길을 0 으로 체크 init(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] < l) visit[i][j] = 1; else if (map[i][j] >= l && map[i][j] <= l + mid) visit[i][j] = 0; else visit[i][j] = 1; } } if (visit[0][0]) continue; // 처음 길도 범위 안에 들어가는지 체크 visit[0][0] = 1; que.push({ 0, 0 }); while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); if (x == (n - 1) && y == (n - 1)){ return 1; } for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < n) { if (visit[nx][ny] == 0) { visit[nx][ny] = 1; que.push({ nx,ny }); } } } } } return 0; } void solve() { int start = 0; int end = maxVal - minVal; while (start <= end) { mid = (start + end) / 2; if (bfs(mid)) end = mid - 1; else start = mid + 1; }
cout << end + 1 << endl; } int main() { problemIn(); solve(); return 0; } |