[백준] 1987 알파벳 / 자바(Java)

문제

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

---

해설

2차원배열에서 4방탐색을 통해 가장 많이 가는 횟수 찾기 문제입니다.

특이한 점은 다른 문제처럼 숫자가 아닌 알파벳으로 2차원 배열이 구성되어있고, 특정 위치의 방문여부가 아닌 특정 알파벳을 방문했는가에 따라 추가탐색의 가능 여부가 갈립니다.

 

문자열이 아닌 알파벳의 방문여부이기 때문에 map을 사용하지 않고 26까지 있는 1차원 배열을 통해 index 0의 값은 A, index 26의 값은 Z를 표현해 쉽게 구분이 가능합니다.

 

재귀를 사용해 다음 위치로 이동하며 재귀별 이동횟수의 max값을 저장해주어 답을 찾아냅니다.

---

코드

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

public class Main{
	static int max;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		max = Integer.MIN_VALUE;
		// 4방탐색 위 우 하 좌
		int dr[] = {-1, 0, 1, 0};
		int dc[] = {0, 1, 0, -1};
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		char[][] board = new char [R][C];
		
		for(int i=0;i<R;i++) {
			board[i] = br.readLine().toCharArray();
		}
		boolean isChecked[]=new boolean [26];
		//초기위치값 지정
		isChecked[board[0][0]-'A'] = true;
		move(0,0,board,isChecked, dr, dc,1);
		System.out.println(max);
		
	}
	
	//cnt -> 이동한 거리(밟은 알파벳 갯수)
	static void move(int r, int c, char [][] board, boolean isChecked[], int[] dr, int[] dc, int cnt) {
		
		max = Math.max(cnt, max);
		//4방탐색
		for(int i=0;i<4;i++) {
			int newr = r+dr[i];
			int newc = c+dc[i];
			// 배열 밖으로 나갈 경우
			if(0>newr || 0>newc || newr>=board.length || newc>=board[0].length) continue;
			
			// 새로 밟은 칸이 이미 밟은 알파벳인경우
			if(isChecked[board[newr][newc]-'A']) continue;
			else { // 처음 밟는 알파벳 인경우
				// 바꾼 알파벳으로 변경
				isChecked[board[newr][newc]-'A'] = true;

				//새로운 이동 진행
				move(newr, newc, board, isChecked, dr, dc, cnt+1);
				// 다시 복구
				isChecked[board[newr][newc]-'A'] = false;
			}
		}
		
	}
}