[백준 1987] 알파벳 (JAVA)
문제
풀이
DFS를 이용해 해결할 수 있습니다. 어떤 알파벳을 거쳐 갔는지 boolean 배열을 이용할 수도 있지만, 알파벳은 총 26자이기 때문에 비트마스킹을 이용해 해결하면 더 빠르게 문제를 해결할 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int R, C, visit, ans = 0;
static int[][] map;
static int[][] check;
static int[][] dt = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[R][C];
check = new int[R][C];
for (int i = 0; i < R; i++) {
char[] input = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
map[i][j] = input[j] - 'A';
}
}
visit = 1 << map[0][0];
dfs(0, 0, 1);
System.out.println(ans);
br.close();
}
static void dfs(int x, int y, int cnt) {
if (check[x][y] == visit) return;
check[x][y] = visit;
for (int d = 0; d < 4; d++) {
int dx = x + dt[d][0];
int dy = y + dt[d][1];
if (dx >= 0 && dx < R && dy >= 0 && dy < C && ((visit & (1 << map[dx][dy])) == 0)) {
visit |= 1 << map[dx][dy];
dfs(dx, dy, cnt + 1);
visit &= ~(1 << map[dx][dy]);
}
}
ans = Math.max(ans, cnt);
}
}
Author And Source
이 문제에 관하여([백준 1987] 알파벳 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@solser12/백준-1987-알파벳-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)