[백준] 1987번 알파벳

1) 생각

알파벳이 각각 적혀있는 R행 C열이 주어졌을 때, (0,0)에서 출발하여 알파벳이 중복되지 않게 최대한 갈 수 있는 칸을 출력하라.

처음 생각

칸을 나아가야 하므로 DFS를 풀이를 해야한다고 생각하였다. 지나간 길에있는 알파벳이 딱 한 번만 나와야 하므로 String 변수에 해당 알파벳을 더해가면서 contains 메소드를 통해 이번에 탐색한 알파벳이 이전에 있었는지 검사하였다.

▶ String 객체를 넘겨주면 검사를 하다보니 시간과 메모리를 크게 잡아먹었다.

▶ 시간도 그렇고 메모리도 18배 정도 차이가 난다.

2) 방안

1) String으로 된 매개변수를 없애고 boolean형 visited 배열을 만들어 주어 해당 알파벳의 위치를 체크하였다.

▶ 다음 탐색을 위해 해당 재귀가 종료될 시 false로 바꿔줬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main{
    static int r,c;
    static char[][] arr;
    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());
        arr = new char[r][c];
        for(int i=0;i<r;i++) {
            String t = br.readLine();
            for(int j=0;j<c;j++)
                arr[i][j] = t.charAt(j);
        }
        visited = new boolean[91];
        solve(0,0,1);
        System.out.println(result);
    }
    
    static int result = 0;
    static boolean[] visited;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve(int x,int y,int cnt) {
        visited[arr[x][y]] = true;
        result = Math.max(cnt, result);
        for(int i=0;i<4;i++) {
            int tx = x+dir[i][0];
            int ty = y+dir[i][1];
            if(tx<0 || ty<0 || tx>=r || ty>=c) continue;
            if(visited[arr[tx][ty]]) continue;
            solve(tx,ty,cnt+1);
        }
        visited[arr[x][y]] = false;
    }
}