(JAVA) 백준 1987번 : 알파벳 -- [DFS]

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

1987번: 알파벳

 

이 문제는 DFS 문제입니다.

 

BFS를 사용하면 모든 경우(상하좌우 및 모든 경로)에 대해 분기처리되서 하나씩 비교해야하기때문에 아닌것 같고

DFS를 사용해서 맞는 경우에만 깊이있게 최대 경로를 탐색해내는게 맞는 것 같아서 DFS를 사용했습니다.

 

알고리즘은 간단해서,

 

  - 1행 1열부터 말 움직이기 시작.
  - 별도 목적지가 없고, 최대로 움직일 수 있는 칸을 구하는 문제기 때문에 DFS(맨 첫 번째칸도 지나간 칸) = 초기값 1
  - R,C(즉, x와 y는 <= 20)
  - 이전까지 지나온 칸에 적힌 알파벳이면 이동 불가능 -> 지금까지 지나온 알파벳 모두 저장 -> boolean 배열로 알파벳 대문자(A ~ Z) 까지를 인덱스로 해서 사용하면 True, 사용하지 않으면 False로 만들어보자.

 

이고,

 

핵심은

 

  1) 지나온 경로에 사용한 알파벳 체크 -> boolean[26], 인덱스 : 해당 지점의 알파벳 - 'A'

  2) DFS 재귀함수 호출 전 알파벳 사용(True), 호출 후 알파벳 미사용 변경(False)

  

인데, 효율성이 높진 않더라구요..

이런 알고리즘으로는 효율적이지만, 다른 정답자의 풀이법을 보니 비트마스킹 활용하는 것 같은데 제가 풀지 않아서 차마 비트마스킹으로 문제풀이 리뷰글을 적을 수 없었습니다..

 

 

 

감사합니다.

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 알파벳
	// DFS
	public class p1987 {
	static int r, c, maxStepCount = 1;
	static char[][] map;
	static int[][] dp;
	static int[] moveX = {0, 1, 0, -1};
	static int[] moveY = {-1, 0, 1, 0};
	static final int A = 'A';
	static boolean[] visited = new boolean[26]; // A-Z 중 방문했던 알파벳
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	r = Integer.valueOf(st.nextToken());
	c = Integer.valueOf(st.nextToken());
	map = new char[r][c];
	dp = new int[r][c];
	// 입력
	for(int i = 0; i < r; i++) {
	String line = br.readLine();
	map[i] = line.toCharArray();
	}
	dp[0][0] = 1;
	dfs(0, 0, 1);
	System.out.println(maxStepCount);
	}
	// 알파벳 사용여부 배열로
	private static int dfs(int x, int y, int count) {
	visited[map[y][x] - A] = true;
	for(int i = 0; i < 4; i++) {
	int nextX = x + moveX[i];
	int nextY = y + moveY[i];
	// map 범위 체크
	if(nextX < 0 || nextX >= c || nextY < 0 || nextY >= r) {
	continue;
	}
	char alphabet = map[nextY][nextX];
	if(visited[alphabet - A]) {
	continue;
	}
	int result = dfs(nextX, nextY, count + 1);
	maxStepCount = Math.max(maxStepCount, result);
	}
	visited[map[y][x] - A] = false;
	return count;
	}
	}

view raw p1987.java hosted with ❤ by GitHub