백준 1987 - 알파벳

Java

1987 번 - 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

접근 방법

간단한 DFS와 Back Tracking 문제이다.
[0,0]에서 시작하여 최대한 갈 수 있는 거리까지 이동한다.
이동하는 방법은 한 좌표에서 [상/하/좌/우]로 각각 이동하여 이동할 수 있는 모든 경우의 수 까지 간다.
이동하다가 더 이상 이동할 수 없으면, 현재까지 간 거리 중 최대 값을 저장한다.

구현

방문한 알파벳을 나타내는 방법은, 26개의 알파벳을 나타내는 0~25 boolean 배열을 선언한다.
알파벳 대문자는 아스키 코드로, A ~ Z == 65 ~ 90 이므로, 각 좌표에 해당하는 알파벳 - ‘A’ 를 하여 0 ~ 26으로 변환한다.
해당하는 값을 인덱스로 하여, 한번 방문한 알파벳이면 boolean 값을 true로 하여 방문하였다고 표시한다.

코드

/*
 * 알파벳
 * https://www.acmicpc.net/problem/1987
 */
import java.util.*;
import java.io.*;

public class Main {
	static int n,m, result = 0;
	static char[][] arr;
	static boolean[][] vis;
	static boolean[] alpha;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	arr = new char[n][m];
    	vis = new boolean[n][m];
    	alpha = new boolean[26];
    	for(int i = 0; i < n; i++) {
    		String str = br.readLine();
    		for(int j = 0; j < m; j++) {
    			arr[i][j] = str.charAt(j);
    		}
    	}
    	
    	DFS(0,0,0);
    	System.out.println(result);
    	br.close();
    }
    // 상 하 좌 우 이동
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    static void DFS(int y, int x, int cnt) {
    	// 범위를 벗어나거나, 이미 방문한 장소거나, 한번 방문한 알파벳이면 종료한다.
    	if(isOutter(y, x) || vis[y][x] || alpha[arr[y][x] - 'A']) {
    		result = Math.max(cnt, result);
    		return; 
    	}
    	// 방문한 알파벳을 표시한다.
    	alpha[arr[y][x] - 'A'] = true;
    	for(int i = 0; i < 4; i++) {
    		DFS(y + dy[i] , x + dx[i], cnt + 1);
    	}
    	// 돌아와서 다른 경로로 이동하기 위해 방문 표시를 지운다
    	alpha[arr[y][x] - 'A'] = false;
    }
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
	// 범위를 벗어나는지 확인하는 함수
    static boolean isOutter(int y, int x) {
    	if(y < 0 || y >= n || x < 0 || x >= m)
    		return true;
    	return false;
    }
}

총평

난이도

⭐⭐★★★

후기

알파벳 방문 처리만 하면 쉬웠던 문제

개선할 점

없