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

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

1987번: 알파벳

 

문제 해석

 

세로 R 칸 가로 C칸으로 된 표 모양의 보드가 존재합니다.

보드의 각 칸에는 알파벳이 하나씩 적혀있고 좌측 상단 칸(0,0)에는 말이 놓여 있습니다.

 

말은 상하좌우 인접한 네 칸 중의 한 칸으로 이동할 수 있습니다.

새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 합니다.

최초에 말이 지나는 칸은 좌측 상단의 칸도 포함됩니다.

 

말이 최대한 몇 칸을 지날 수 있는지 구하는 프로그램을 작성하세요.

 

 

문제 풀이 전 설계

중복을 제거해주는 HashMap을 사용하면 좋을 것 같습니다.

BFS를 하면서 한칸씩 앞으로 나아가게 될 때 어떻게 중복 제거를 할 것인가?

BFS는 힘들 것 같다는 생각이 들었습니다.

DFS를 사용한다면 괜찮을 것 같습니다 DFS를 통해 완전 탐색을 해야 합니다.

최대 칸 수를 구해야 하기 때문에 백 트레킹도 힘들 것 같습니다.

 

코드

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

class Hourse {
	int y;
	int x;
	int moveCount;

	public Hourse(int y, int x) {
		super();
		this.y = y;
		this.x = x;
		moveCount = 1;
	}

	@Override
	public String toString() {
		return "Hourse [y=" + y + ", x=" + x + ", moveCount=" + moveCount + "]";
	}

}

public class Main_1987_알파벳 {

	static char[][] board;

	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static final int Direction = 4;
	static int R, C;
	static int moveDistance = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		board = new char[R][C];
		for (int y = 0; y < R; y++) {
			String tempRow = br.readLine();
			for (int x = 0; x < C; x++) {
				board[y][x] = tempRow.charAt(x);
			}
		}
		Set<Character> hashSet = new HashSet<Character>();
		Hourse hourse = new Hourse(0, 0);
		// 현재 말의 위치는 0,0 moveCount = 1으로 설정해서 처음에도 움직이는 취급
		hashSet.add(board[0][0]);
		DFS(hourse, hashSet);
		System.out.println(moveDistance);
	}

	private static void DFS(Hourse hourse, Set<Character> hashSet) {
		for (int k = 0; k < Direction; k++) {
			int originY = hourse.y;
			int originX = hourse.x;
			int tempY = hourse.y + dy[k];
			int tempX = hourse.x + dx[k];

			if (!isPosValid(tempY, tempX)) {
				continue;
			}

			char alphabet = board[tempY][tempX];

			if (isDuplicated(alphabet, hashSet)) {
				moveDistance = hourse.moveCount > moveDistance ? hourse.moveCount : moveDistance;
				continue;
			}

			hourse.x = tempX;
			hourse.y = tempY;
			hourse.moveCount++;
			hashSet.add(alphabet);

			DFS(hourse, hashSet);

			hourse.x = originX;
			hourse.y = originY;
			hourse.moveCount--;
			hashSet.remove(alphabet);

		}
	}

	private static boolean isPosValid(int tempY, int tempX) {
		return (tempY >= 0 && tempX >= 0 && tempY < R && tempX < C);
	}

	private static boolean isDuplicated(char alphabet, Set<Character> hashSet) {
		return hashSet.contains(alphabet);
	}

}