1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
문제에서 요구하는 조건은
1. 말은 (0, 0)에서 출발합니다.
2. 말은 상하좌우 방향으로 움직일 수 있습니다.
3. 말이 지나가는 동안 밟은 칸의 알파벳은 모두 달라야합니다.
말이 (0, 0)에서 출발하여 지나갈 수 있는 최대의 칸 수를 출력해야합니다.
저는 백트래킹으로 해결하였고 해당 칸을 방문체크하는 visit배열과 칸에 있는 알파벳 중복체크를 위한 alphachk 배열을 사용하였습니다.
재귀를 돌릴때마다 답을 갱신해주고, 해당 칸과 알파벳에 방문처리합니다.
그 다음 4방향 탐색하여 맵 밖으로 나갔는지, 이미 방문하였거나 밟은 적이 있는 알파벳인지 체크를 해줍니다.
모두 통과하면 nx, ny, cnt+1를 재귀로 넘겨주고, 빠져나오면 true했던 boolean배열을 모두 false로 바꿔줍니다.
마지막으로 정답을 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static boolean visit[][], alphachk[];
static char list[][];
static int N, M, ans;
static void dfs(int x, int y, int cnt) {
ans = Math.max(ans, cnt);
visit[x][y] = true;
alphachk[list[x][y] - 'A'] = true;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (visit[nx][ny] || alphachk[list[nx][ny] - 'A'])
continue;
dfs(nx, ny, cnt + 1);
alphachk[list[nx][ny] - 'A'] = false;
visit[nx][ny] = false;
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new char[N][];
visit = new boolean[N][M];
alphachk = new boolean[26];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
dfs(0, 0, 1);
System.out.println(ans);
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 14500 테트로미노 (0) | 2021.03.15 |
|---|---|
| boj 16922 로마 숫자 만들기 (0) | 2021.02.24 |
| boj 3109 빵집 (0) | 2021.02.18 |
| boj 17406 배열 돌리기 4 (0) | 2021.02.10 |
| boj 16927 배열 돌리기 2 (0) | 2021.02.10 |