혼종 꼬지마루
[백준] 1103 - 게임 본문
https://www.acmicpc.net/problem/17070
이 문제와 상당히 유사하고,
2019/10/13 - [Algorithms/DP] - [백준] 17070 - 파이프 옮기기에 위 문제의 풀이를 포스팅 하였으니 왜 같다고 생각한지 확인 해보시길...
먼저 이 문제는 dfs로 풀면 아주, 상당히, 시간이 걸릴 문제다.
그렇기 때문에, dfs에 dp를 먹여서 가지도 쳐 주고, 무한 루프도 쉽게 찾을 수 있다.
한번 끝까지 간(범위를 벋어나거나, 구멍에 빠지거나) 한 동전은 돌아오며 그 길이를 저장한다.
즉, 좌표에 끝까지 갔을 경우, 최대 몇번까지 움직일 수 있는지를 저장한다.
한마디로 구멍이나, 범위를 벋어난 동전은 재귀 호출에 return 할때 1, 2, 3....순으로 돌아오는 좌표에 저장이 될 것이다.
만약 다른 경로로 탐색하다 이미 지났던 점을 만날 경우, 지났던 점의 좌표에 해당하는 dp값을 return 받으며 1씩 증가시키며 return한다.
즉, 그 경로로 가다보면, 어짜피 지나왔던 점에 횟수만큼 더 움직일 것이니, 더 탐색할 것 없이 return을 받으면 된다~~ 라는 논리가 된다.
그럼 무한루프는 어떻게 check를 해 주느냐? 단순하다
그냥 visit배열 하나로 방문점만 제 때 체크해주면 된다.
여기서 혼동할 점은, dp에서 이미 방문했던 점은 왜 안되느냐? 라는 것인데, 그건 다른 중간이 다른 경로고, 결과는 같다 라는 점이다.
집에서 세탁소에 들렀다 편의점을 간다고 가정할 때, 왼쪽골목으로 돌아서 세탁소를 거쳐 편의점을 가느냐, 오른쪽 골목으로 돌아서 세탁소를 거쳐 편의점을 가느냐 그 차이일 뿐...!
무한 loop는 지금 가는 경로에서 방문한 점을 만났을 경우만 성립함으로 그 경우만 check해주면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <iostream> #include <cstdio> #include <cstdlib> #include <memory.h> #define SIZE 52 #define MAX(X, Y) (X) > (Y) ? (X) : (Y) using namespace std; int map[SIZE][SIZE], dp[SIZE][SIZE], visit[SIZE][SIZE]; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; int N, M; int dfs(int x, int y) { if (x < 0 || y < 0 || x >= M || y >= N || !map[y][x]) return 0; if (visit[y][x]) { cout << -1 << endl; exit(0); } if (dp[y][x]) return dp[y][x]; visit[y][x] = 1; for (int i = 0; i < 4; i++) dp[y][x] = MAX(dp[y][x], dfs(x + map[y][x] * dx[i], y + map[y][x] * dy[i]) + 1); visit[y][x] = 0; return dp[y][x]; } int main(void) { cin >> N >> M; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { char c; cin >> c; if (c <= '9') map[i][j] = c - '0'; } cout << dfs(0, 0) << endl; return 0; } | cs |
'Algorithms > DP' 카테고리의 다른 글
[백준] 17070 - 파이프 옮기기 (0) | 2019.10.13 |
---|---|
[백준] 4095 - 최대 정사각형 (0) | 2019.05.05 |
[백준] 15559 - 내 선물을 받아줘 (0) | 2019.04.13 |
[백준] 1520 - 내리막길 (0) | 2018.09.14 |
[백준] 9465 - 스티커 (0) | 2018.09.08 |