[Week14] 해저탐사선

이문제는 혼자 못풀었다...정말 어려웠다..

DFS로 풀면 되겠지 했는데..

대체 어디서 visit를 풀어줘야되고 어디서 안풀어줘야되고를 몰랐다

근데 이게 웬걸..

http://blog.eairship.kr/268 깔끔하게 정리해놓은 DFS의 이론 아래에 이것과 비슷한 문제가 있었다

단지 이 사이트의 문제는 시작과 끝점이 정해져있고 minimum을 찾는것이고

그리고 문제해결기법의 문제는 시작점만 있고 maximum을 찾는 것이다.

그렇다면!!! 그 두개의 조건만을 변경해주면 되는 것이다.

아 잡힐듯 말듯해서 풀지 못했는데 이렇게 쉽게 풀리다니

이제 정신 똑디 잡고 문제 풀어야겠다

이 문제의 내가 헷갈린 가장 큰 visit라는 부분은

map을 변경하여 간단하게 해결되었다

어짜피 1인 부분은 visited로 설정해줬기때문에 안갈꺼고 0인부분만 갈텐데

지나간 0인 부분을 1로 대체하고 그 값이 visit도 대체해주고있다.

크.. 메모리 절약

한번 돌아간 부분은 1로 해주고 만약 어느 방향에서도 가지 못한다면 return

저 함수는 전체를 다 도는 함수이다

역시 모든 경우를 다 돌려면 DP..

아 그리고 이전에 내가 음..적용하지 못했던 것은 바로 cache이다.

만약 지나간 부분의 자리에 최대 몇개가 들어있는지 max값으로 저장할 수 있다면 그리고 나중에 그곳에 도달했을때 다시 return을 해주면

얼마나 빠를까 생각했다.

하지만 생각보다 까다로웠던 것 같다.

#include<iostream> #include <vector> #include <algorithm> #include <fstream> using namespace std; #define VISITED 1 #define DIDNT_VISIT 0 int answer = 0, map_count; vector<vector<int>>map,cache; void DFS(int x, int y, int count) { if (cache[x][y] > count) return; else cache[x][y] = count; answer = max(answer, count); map[x][y] = VISITED; if (x + 1 < map_count && map[x + 1][y] == DIDNT_VISIT) DFS(x + 1, y, count + 1); if (y + 1 < map_count && map[x][y + 1] == DIDNT_VISIT) DFS(x, y + 1, count + 1); if (x - 1 >= 0 && map[x - 1][y] == DIDNT_VISIT) DFS(x - 1, y, count + 1); if (y - 1 >= 0 && map[x][y - 1] == DIDNT_VISIT) DFS(x, y - 1, count + 1); map[x][y] = DIDNT_VISIT; } int main() { ifstream fcin; fcin.open("B_ex_input.txt"); ofstream fcout; fcout.open("B_small_answer.txt"); int for_count, index_count, x, y; fcin >> for_count; while (for_count--) { fcin >> map_count >> index_count; map = vector<vector<int>>(map_count, vector<int>(map_count)); for (int j = 0; j < map_count; j++) for (int k = 0; k < map_count; k++) fcin >> map[j][k]; for (int j = 0; j < index_count; j++) { cache = vector<vector<int>>(map_count, vector<int>(map_count,0)); fcin >> x >> y; answer = 0; DFS(x, y, 0); for (int j = 0; j < map_count; j++) { for (int k = 0; k < map_count; k++) cout << cache[j][k]<<" "; cout << endl; } cout << answer + 1 << endl; } } system("pause"); }

이 코드가 처음에 cache로 짠 코드이다

사실 저 코드에 조금 변형시켜봤는데

처음에는 visit도 있었고 if마다마다 visit도 변형시켰고

그리고 저 cache도 더 복잡했다.

일단 저걸 실행해보면 

위의 그림의 예제에서

이러한 값이 나온다

일단 안간 부분이랑 처음부분은 0으로 설정했으니 어쩔 수 없었다

하지만 주목해야할 점은 바로 6이다 저 값이 돌고 돌아 저기에 저장되었다 하지만 만약에

0->1->6으로 가면 조금 더 큰 값을 얻을 수 있다.

결국 마지막값이 더 큰 수가 나온다는 것이다.

하지만 현재가 6이기때문에 섯부른 판단을 했다

6이므로 지금 들어오는 애보다는 크니까 더 큰수이겠지 라고 판단한 것이다

결국 cache를 빼야했다

그래서 정답 코드를 만들었다.

#include<iostream> #include <vector> #include <algorithm> #include <fstream> using namespace std; #define VISITED 1 #define DIDNT_VISIT 0 int answer = 0, map_count; vector<vector<int>>map; void DFS(int x, int y, int count) { answer = max(answer, count); map[x][y] = VISITED; if (x + 1 < map_count && map[x + 1][y] == DIDNT_VISIT) DFS(x + 1, y, count + 1); if (y + 1 < map_count && map[x][y + 1] == DIDNT_VISIT) DFS(x, y + 1, count + 1); if (x - 1 >= 0 && map[x - 1][y] == DIDNT_VISIT) DFS(x - 1, y, count + 1); if (y - 1 >= 0 && map[x][y - 1] == DIDNT_VISIT) DFS(x, y - 1, count + 1); map[x][y] = DIDNT_VISIT; } int main() { ifstream fcin; fcin.open("B_small_input.txt"); ofstream fcout; fcout.open("B_samll_answer.txt"); int for_count, index_count, x, y; fcin >> for_count; while (for_count--) { fcin >> map_count >> index_count; map = vector<vector<int>>(map_count, vector<int>(map_count)); for (int j = 0; j < map_count; j++) for (int k = 0; k < map_count; k++) fcin >> map[j][k]; for (int j = 0; j < index_count; j++) { fcin >> x >> y; answer = 0; DFS(x, y, 1); fcout << answer << endl; } } system("pause"); }