백준 1987번: 알파벳
문제 설명
- 말이 가장 길게 움직일 수 있는 경우의 수를 구하는 문제입니다.
접근법
- 길을 탐색해보고 해당 길이 틀렸으면 다시 되돌아와 새로운 길을 가는 백트래킹을 활용할 수 있습니다.
- 알파벳 길이만큼의 배열을 활용해 중복되는 순간을 체크합니다.
정답
package simple_test;
import java.util.*;
public class Main {
static int r;
static int c;
static char[][] board;
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static boolean[] v;
static int max;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
v = new boolean[26];
board = new char[r][c];
for (int i = 0; i < r; i++) {
board[i] = sc.nextLine().toCharArray();
}
BackT(0, 0, 0);
System.out.println(max);
}
public static void BackT(int x, int y, int cnt) {
if (v[board[x][y] - 'A']) {
max = Math.max(max, cnt);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < r && 0 <= ny && ny < c) {
v[board[x][y] - 'A'] = true;
BackT(nx, ny, ++cnt);
v[board[x][y] - 'A'] = false;
--cnt;
}
}
}
}
Author And Source
이 문제에 관하여(백준 1987번: 알파벳), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-1987번-알파벳저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)