[코딩 테스트- Java] 백준1987 - 알파벳

INPUT

첫째 줄에 R과 C
R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳

OUTPUT

말이 지날 수 있는 최대의 칸 수

CONSTRAINTS

1 <= R,C <= 20
한번 지나온 알파벳은 다시 방문할 수 없다. EX) A->B->(다른 위치의)A 는 불가능

LOGIC

DFS를 이용하여 완전탐색을 실시한다.
재귀를 이용해서, 최대한 멀리 갈 수 있는 길이를 업데이트 해주면 된다.

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class baek1987 {

	// 4가지 방향으로 가기 위함
    private static final int[] dx = {1,-1,0,0};
    private static final int[] dy = {0,0,1,-1};
    
    // r 과 c 는 map의 사이즈, answer 는 재귀 돌면서 값 업데이트 용도
    static int r, c, answer;
	
    // 방문한 알파벳인지 확인용 배열. 재귀 돌면서 값 업데이트 용도
    static boolean[] visitedChar;
    public static void main(String[] args) throws IOException {
    	// 초기 인풋 설정
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] size = br.readLine().split(" ");
        r = Integer.parseInt(size[0]);
        c = Integer.parseInt(size[1]);

        char[][] board = new char[r][c];
        for (int i = 0; i < r; i++) {

            String data = br.readLine();

            for(int j=0; j<c; j++){

                board[i][j]=data.charAt(j);
            }
        }

		// 알파벳은 26개 이다. 0번째 인덱스는 A를 방문했는지, 25번째 인덱스는 Z를 방문했는지 나타낸다.
        visitedChar = new boolean[26];
		
        // 특정 알파벳-'A' 는 해당 알파벳이 몇 번째 알파벳인지 나타내줌
        visitedChar[board[0][0]-'A']=true;
        
        // 답을 저장할 공간 (전역변수)
        answer=0;
        
        // 재귀 실행
        dfs(0,0,1,board);

        System.out.println(answer);
    }
	
    // 재귀적으로 탐색하는 메소드
    public static void dfs(int x, int y, int count, char[][] board){
        // 매 호출 시 마다 업데이트
        answer = Math.max(answer,count);
        
        // 4가지 방향으로
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
			
            // 인덱스를 벗어나지 않는지 확인
            if (newX < r && newY < c && newX >= 0 && newY >= 0) {
				
                // 해당 알파벳이 방문 된 알파벳인지 확인
                if (!visitedChar[board[newX][newY]-'A']){
                	// 해당 알파벳 방문
                    visitedChar[board[newX][newY]-'A']=true;
                    // 새로운 좌표로 길이+1 한 상태로 다시 탐색
                    dfs(newX,newY,count+1, board);
                    // 재귀를 위해 이전 방문 삭제
                    visitedChar[board[newX][newY]-'A']=false;
                }
            }
        }
    }
}

회고

처음에 방문 할 알파벳이 중복이 되면 안되기 때문에 Set을 이용하려고 했다. Set 의 add 메소드를 사용하면 중복인지 아닌지를 판별 해주기 때문에 될거라고 생각했지만, 해당 시간복잡도는 Set 의 길이가 N 일때 O(N) 이여서 시간 초과는 나지 않았지만 2200ms 가 걸렸다.

그래서 boolean 배열을 사용했다. 어차피 26칸짜리 배열이고, 방문 여부를 인덱스를 이용해 접근하면 시간복잡도를 많이 아낄 수 있다.

-> 시간이 800ms 로 줄었다.
방문 여부는 최대한 인덱스 기반으로 접근해야겠다.