[BOJ/JAVA] 백준 1987 : 알파벳 (자바)

문제 정보

  문제명   - 알파벳
  난이도   - 골드 IV
문제 번호 - 1987번

---

문제 링크

BOJ_G4_1987_알파벳

1987번: 알파벳

---

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

---

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)
둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

---

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
2 4 CAAB ADCB	3
3 6 HFDFFB AJHGDH DGAGEH	6
5 5 IEFCJ FHFKC FFALF HFGCF HMCHH	10

---

알고리즘 분류

● 그래프 이론
● 그래프 탐색
● 깊이 우선 탐색 (BFS)
● 백트래킹 (Backtracking)

---

소스코드

package Lv3_Gold;
/*
 * 풀면서 배운 점
 * DFS 탐색은 동일하나 이중배열로 string값을 비교하는것보다 아스키 코드로 짰을 때 훨씬 효율적이었음.
 * string값 비교 	-> 메모리 : 295700 KB, 시간 : 3364 ms
 * 아스키값 사용 	-> 메모리 :  12432 KB, 시간 :  844 ms
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 깊이 우선 탐색(DFS), 백트래킹(Backtracking)
 * https://www.acmicpc.net/problem/1987
 */
public class BOJ_G4_1987_알파벳 {
	static int R, C, result = 0;
	static char[][] alphabet;
	static boolean[] isVisited;
	// 상, 하, 좌, 우
	static int[] dRow = {-1, 1, 0, 0};
	static int[] dCol = { 0, 0,-1, 1};
	
	public static void dfs(int Row, int Col, int count) {
		// 최대 이동값 최신화
		result = Math.max(result, count);
		// 상, 하, 좌, 우 이동
		for (int index = 0; index < 4; index++) {
			int now_Row = Row + dRow[index];
			int now_Col = Col + dCol[index];
			// 범위 내에 있고 || 해당 알파벳에 방문하지 않았다면 (방문확인시에 now값을 사용하기 때문에 무조건 마지막에 비교해줘야함)
			if(now_Row >= 0 && now_Row < R && now_Col >= 0 && now_Col < C && !isVisited[alphabet[now_Row][now_Col]-'A']) {
				// 다음 알파벳 true로 변경 -> dfs -> 알파벳 false로 변경
				isVisited[alphabet[now_Row][now_Col]-'A'] = true;
				dfs(now_Row, now_Col, count+1);
				isVisited[alphabet[now_Row][now_Col]-'A'] = false;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		// RxC 크기의 보드
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		alphabet = new char[R][C];
		// A~Z 크기의 알파벳 체크 배열 생성 및 입력
		isVisited = new boolean['Z'-'A'+1];
		for (int i = 0; i < R; i++) {
			alphabet[i] = br.readLine().toCharArray();
		}
		// (0,0) 지점의 알파벳 방문, count: 1부터 시작 초기값 설정
		isVisited[alphabet[0][0] - 'A'] = true;
		dfs(0,0, 1);
		System.out.println(result);
		br.close();
	}
}

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---