TENSOR STUDIO
세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ( $1$행 $1$열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 $R$과 $C$가 빈칸을 사이에 두고 주어진다. ( $1 ≤ R,C ≤ 20$) 둘째 줄부터 $R$개의 줄에 걸쳐서 보드에 적혀 있는 $C$개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
2 초 256 MB
2 4 CAAB ADCB
3
처음에는 백트래킹을 위해 지금까지 지나온 경로를 모두 기억하는 무식한 방법으로 접근했다. 하지만 이 방법은 풀이는 성공했지만 메모리 조건을 초과해서 메모리 초과가 발생했다. (그 와중에도 파이썬으로는 풀이가 성공했지만 자바로는 메모리 초과가 발생했다는 점이 재밌다. 아무래도 파이썬의 메모리 보정이 꽤 크기도 하고, 파이썬으로 문제풀이를 하던 습관 때문에 파이썬의 리스트에 대응되는 자바의 ArrayList를 남발하면서 메모리 초과가 발생했던 것 같다.)
그래서 백트래킹을 위해 지금까지 지나온 경로를 모두 기억하는 것이 아니라 알파벳의 원소별로 방문 여부를 체크하는 방법으로 접근했다. 이 방법은 메모리 초과가 발생하지 않았다.
사실 BFS 또는 DFS로 접근하는데 있어서, 개인적으로는 재귀로 구현하는 DFS는 메모리 초과가 발생할 가능성이 크기 때문에 되도록이면 피하는 방법이지만 이번에는 재귀로 구현한 DFS로 풀이했다.
또한 98%의 테스트케이스에서 멈췄는데, 역시나 이는 입력 : 1 1 / A 일때, 1이 출력되어야 하는데 0이 출력되었기 때문이다. 이는 최소한 한 번은 이동해야 answer에 값이 할당되는데, 그렇지 않아서 발생한 문제였다. 이런 실수를 하지 말아야 한다고 생각하는데, 안타깝다 ㅠㅠ
아, 그리고 어차피 알파벳은 26개이기 떼문에 26이 넘어가면 더 이상 탐색할 필요가 없다.
package boj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class newboj1987 {
// 상하좌우 순서로 방향배열 선언
static int R, C;
static int[][] theMap;
static int[] x_way = {-1, 1, 0, 0};
static int[] y_way = {0, 0, -1, 1};
static int answer = 0;
static boolean[] visited = new boolean[26];
public static void dfs(int x, int y, int count) {
//answer를 1로 초기화 하거나 문제공간이 1, 1인 경우에는 1로 리턴해도 된다.
if (R == 1 && C == 1) {
answer = 1;
return;
}
// 26개 이상의 알파벳을 지나면 더 이상 탐색할 필요가 없다.
if (count >= 26) {
answer = count;
return;
}
// 이미 방문한 알파벳이라면 answer에 count를 할당하고 리턴한다.
if (visited[theMap[x][y]]) {
answer = Math.max(answer, count);
return;
}
else {
visited[theMap[x][y]] = true;
ArrayList<int[]> moveList = ableMove(x,y);
for(int[] coordinates : moveList) {
dfs(coordinates[0], coordinates[1], count+1);
}
}
visited[theMap[x][y]] = false;
}
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());
theMap = new int[R][C];
for (int i = 0; i < R; i++) {
String str = br.readLine();
for (int j = 0; j < C; j++) {
theMap[i][j] = str.charAt(j) - 'A';
}
}
dfs(0, 0, 0);
System.out.println(answer);
}
public static ArrayList<int[]> ableMove(int x, int y) {
ArrayList<int[]> coordinates = new ArrayList<>();
for(int i = 0; i < 4; i++) {
int x_position = x + x_way[i];
int y_position = y + y_way[i];
// 배열을 벗어나지 않는지 체크
if(x_position < 0 || x_position > theMap.length-1 || y_position < 0
|| y_position > theMap[0].length-1 ){
}
else {
int[] temp = {x_position, y_position};
coordinates.add(temp);
}
}
return coordinates;
}
}