https://www.acmicpc.net/problem/17090
17090번: 미로 탈출하기
크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문
www.acmicpc.net
https://emoney96.tistory.com/24
boj 1103 게임
https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여
emoney96.tistory.com
dfs + dp 문제이며 위의 문제와 비슷한 방법으로 해결하였습니다.
대신 게임 문제는 방향이 정해져있지 않아서 4방향 모두 확인해야하지만 이 문제는 1방향만 확인하면 되는 문제입니다.
현재 좌표의 방향으로 이동하면서 맵 밖으로 나가면 1을 리턴, visit으로 사이클을 체크해서 사이클이 발생했으면 0을 리턴합니다.
N * M번 모두 돌려가면서 ans를 구하였습니다.
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
|
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[510][510];
static boolean visit[][] = new boolean[510][510];
static int dp[][] = new int[510][510];
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 0;
visit[x][y] = true;
if (dp[x][y] != -1)
return dp[x][y];
int d = 0;
if (list[x][y] == 'D')
d = 1;
else if (list[x][y] == 'R')
d = 0;
else if (list[x][y] == 'U')
d = 3;
else
d = 2;
int nx = x + direct[d][0];
int ny = y + direct[d][1];
if (nx < 0 || nx >= N || ny < 0 || ny >= M)
dp[x][y] = 1;
else {
dp[x][y] = dfs(x + direct[d][0], y + direct[d][1]);
visit[nx][ny] = false;
}
return dp[x][y];
}
static void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dp[i][j] != -1) {
ans += dp[i][j];
continue;
}
ans += dfs(i, j);
visit[i][j] = false;
}
}
System.out.println(ans);
}
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();
Arrays.fill(dp[i], -1);
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
|---|---|
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |
| boj 1648 격자판 채우기 (0) | 2021.06.22 |
| boj 14700 넴모넴모 (Hard) (0) | 2021.06.22 |
| boj 1311 할 일 정하기 1 (0) | 2021.06.21 |