https://www.acmicpc.net/problem/1103
1103번: 게임
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는
www.acmicpc.net
그냥 dfs돌리다가 시간초과난 적이 있어서 dp를 같이 사용하였습니다.
보드에 적혀있는 숫자에 맞춰서 동전을 움직여서 최대 몇 번 움직일 수 있는지 구하는 문제입니다.
중간에 있는 구멍은 무시해도 되고, 도착지점이 구멍인 경우에는 동전이 빠지므로 이동하지 못합니다.
dfs로 모든 경우를 다 돌아보고 횟수를 구하면 됩니다.
예외처리로 무한루프가 있는 경우 -1을 출력해야하는데, dfs를 돌다가 방문처리된 곳에 다시 한 번 가게 되면 무한루프 판정으로 -1을 리턴하게 구현하였습니다.
|
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static char list[][] = new char[50][50];
static boolean visit[][] = new boolean[50][50];
static int dp[][] = new int[50][50];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M, ans;
static int dfs(int x, int y) {
if (visit[x][y])
return ans = -1;
visit[x][y] = true;
if (dp[x][y] != -1)
return dp[x][y];
dp[x][y] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0] * (list[x][y] - '0');
int ny = y + direct[i][1] * (list[x][y] - '0');
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (list[nx][ny] == 'H')
continue;
dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
if (ans == -1)
return ans;
visit[nx][ny] = false;
}
return dp[x][y];
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
}
}
public static void main(String[] args) throws Exception {
input();
ans = dfs(0, 0);
if (ans != -1)
ans++;
System.out.println(ans);
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 9657 돌 게임 3 (0) | 2021.01.27 |
|---|---|
| boj 2096 내려가기 (0) | 2021.01.22 |
| boj 12852 1로 만들기 2 (0) | 2021.01.22 |
| boj 16195 1, 2, 3 더하기 9 (0) | 2021.01.22 |
| boj 15993 1, 2, 3 더하기 8 (0) | 2021.01.22 |