혼종 꼬지마루
[백준] 15559 - 내 선물을 받아줘 본문
기존 값을 저장하고, 그걸 불러와야 답을 구할 수 있다... 그래서 메모이제이션이 중요하기 때문에 DP라고 생각함
1. 순차적으로 map을 검사하면서 방문하지 않은 지점이라면 DFS로 탐색
2. 방문한 지점이라면 그 방문한 지점의 값을 반환
3. 이렇게 끝까지 같다가 돌아오면 리턴된 값과 답을 비교하여 답을 찾아준다.
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 38 39 40 41 42 43 44 45 46 | #include <iostream> #define MAXSIZE 1002 using namespace std; char map[MAXSIZE][MAXSIZE]; int visit[MAXSIZE][MAXSIZE]; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; int N, M; int dir(const char buff) { switch (buff) { case'N': return 0; case'S': return 1; case'W': return 2; case'E': return 3; default: return -1; } } int dfs(int x, int y, int cnt) { if (visit[y][x]) return visit[y][x]; visit[y][x] = cnt; int d = dir(map[y][x]); int nx = x + dx[d], ny = y + dy[d]; visit[y][x] = dfs(nx, ny, cnt); return visit[y][x]; } int calc() { int ret = 0; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (!visit[i][j]) { visit[i][j] = dfs(j, i, ret + 1); ret = ret > visit[i][j] ? ret : visit[i][j]; } return ret; } int main(void) { cin >> N >> M; for (int i = 0; i < N; i++) cin >> map[i]; cout << calc() << '\n'; return 0; } | cs |
'Algorithms > DP' 카테고리의 다른 글
[백준] 17070 - 파이프 옮기기 (0) | 2019.10.13 |
---|---|
[백준] 4095 - 최대 정사각형 (0) | 2019.05.05 |
[백준] 1520 - 내리막길 (0) | 2018.09.14 |
[백준] 9465 - 스티커 (0) | 2018.09.08 |
[백준] 11048 - 이동하기 (0) | 2018.08.29 |