[백준 / Java] 1987번: 알파벳 (골드4)

문제 풀이 날짜: 2023.08.18
포스트 작성일: 2023.08.23

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1987번: 알파벳 (골드4)

 

키워드

DFS(깊이 우선 탐색)

 

풀이 접근법

• DFS로 풀이한다. 보드 규격에 맞추어 4방 탐색을 한다.
• 원래 시간 제한이 다소 빡빡한 문제라 느릴 만한 부분은 최대한 제거하는 것이 좋다.
• Set은 매우 느린 자료구조이다 ⇒ 따라서 Set에 지금까지 방문한 알파벳을 넣지 않고도 더욱 효율적으로 관리하는 방법이 필요하다.
  • 이를 위해 각 알파벳의 방문 여부를 boolean 배열로 관리한다.
  • 이미 방문한 적 있는 알파벳을 다시 방문하였다면 그곳을 방문하지 않고(continue) delta값을 바꾸어 방향을 전환한다.

 

코드

import java.io.*;

public class Main {

	private static int R;
	private static int C;
	
	private static char[][] board;
	
	private static int[] dr = {0, 1, 0, -1};
	private static int[] dc = {1, 0, -1, 0};
	
	private static int maxDepth = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");

		R = Integer.parseInt(temp[0]);
		C = Integer.parseInt(temp[1]);
		
		board = new char[R][C];
		
		boolean[] alphabets = new boolean['Z' - 'A' + 1];
		
		for(int i = 0; i < R; i++) {
			String line = br.readLine();
			for(int j = 0; j < C; j++) {
				board[i][j] = line.charAt(j);
			}
		}
		
		alphabets[board[0][0] - 'A'] = true;
		DFS(0, 0, alphabets);
		
		System.out.println(maxDepth);
	}

	private static void DFS(int r, int c, boolean[] alphabets) {
		if(r == R && c == C) {
			return;
		}
		
		int sum = 0; //maxDepth 계산
		for(boolean b : alphabets) {
			if(b) sum += 1;
		}
		maxDepth = Math.max(maxDepth, sum);
		
		int nr = 0;
		int nc = 0;
		for(int i = 0; i < dr.length; i++) {
			nr = r + dr[i];
			nc = c + dc[i];
			
			if(!isValid(nr, nc)) {
				continue;
			}
			
			if(alphabets[board[nr][nc] - 'A']) {
				continue;
			}
			
			alphabets[board[nr][nc] - 'A'] = true;
			DFS(nr, nc, alphabets);
			alphabets[board[nr][nc] - 'A'] = false;
		}
		
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < R && nc < C);
	}

}

---

 

 

git 링크

(git 링크 첨부)