백준 1103, DP, DFS
DP 와 DFS 를 같이 사용하는 문제.
$ dp(x, y, dir) $ 는 $ (x, y) $ 에서 $ dir $ 방향으로 탐색할 때 최대 탐색 가능한 횟수를 의미한다.
cycle이 생긴다면 무한히 탐색을 계속 할 수 있기 때문에,
dfs 를 통해 cycle 판정을 덤으로 같이 해주면 된다.
쉬운 문제인데 많이 헤매서 공부를 더 많이 해야한다는 생각이 들었다.
Source Code
//BOJ1103
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define Msize 55
#define INF 123456789
int board[Msize][Msize], cache[Msize][Msize][4];
int N, M;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool isInside(int x, int y) {
if (x<1 || x>N || y<1 || y>M) return false;
else return true;
}
bool visited[Msize][Msize];
int dp(int x, int y, int dir) {
if (!isInside(x, y)) return 0; // 탈출
if (board[x][y] == -1) return 0;// 구멍
if (visited[x][y]) return INF;//cycle 이 생겼다면 INF
int& ret = cache[x][y][dir];
if (ret != -1) return ret;
visited[x][y] = true;
int dist = board[x][y];
for (int i = 0; i < 4; ++i) {
int tmp = 1 + dp(x + dist * dx[dir], y + dist * dy[dir], i);
ret = max(ret, tmp);
if (ret > INF) ret = INF;
}
visited[x][y] = false;
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 1; i <= N; ++i) {
string s;
cin >> s;
for (int j = 1; j <= M; ++j) {
board[i][j] = s[j - 1];
if (board[i][j] == 'H') board[i][j] = -1;
else board[i][j] -= '0';
}
}
int ans = -1;
memset(cache, -1, sizeof(cache));
memset(visited, 0, sizeof(visited));
for (int i = 0; i < 4; ++i) {
ans = max(ans, dp(1, 1, i));
//(1,1) 에서 4 방향 탐색
}
if (ans == INF) printf("-1\n");
else printf("%d\n", ans);
return 0;
}
PREVIOUSBOJ 11402