[Java Algorithm] 알파벳 BOJ #1987

문제

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

 

내 문제 풀이

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

public class Main {
	
	static int r, c;
	static char[][] board;
	static int max = 0;
	
	public static void dfs(int x, int y, boolean[] alphabet, int cnt) {
		if(x < 0 || y < 0 || x >= r || y >= c) return;
		if(alphabet[(int)board[x][y]-65]) { // 이미 쓰여진 알파벳 만날 시 리턴
			max = Math.max(max, cnt);
			return;
		}
		
		alphabet[(int)board[x][y]-65] = true; // 현재 알파벳이 쓰였음을 표시
		dfs(x-1, y, alphabet, cnt+1);
		dfs(x, y-1, alphabet, cnt+1);
		dfs(x+1, y, alphabet, cnt+1);
		dfs(x, y+1, alphabet, cnt+1);
		alphabet[(int)board[x][y]-65] = false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(in.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		board = new char[r][c];
		for(int i = 0; i < r; i++) {
			String now = in.readLine();
			for(int j = 0; j < c; j++) {
				board[i][j] = now.charAt(j);
			}
		}
		
		dfs(0, 0, new boolean[26], 0);
		System.out.println(max);
	}

}

👉 DFS 문제

• 탐색마다 어떤 알파벳이 쓰였는지 체크해줄 alphabet 배열을 만들어주었다.
  첫 번째 인덱스부터 알파벳 순서대로 체크할 수 있도록 했는데,
  체크할 때는 해당하는 알파벳을 int형으로 변환한 후, 65를 빼주어 인덱스로 사용했다.
• dfs 탐색마다 쓰인 알파벳을 체크하고, 몇 번째 알파벳인지 카운팅해주었는데,
  이미 쓰여진 알파벳을 또다시 만나면 그 때는 max 값을 갱신하고 리턴했다.

 

💡 피드백

• 쉽게 풀 수 있는 문제였다. 하지만! 시간 복잡도가 넘 안좋아서 다시 한 번 봐야 할 듯 싶다.