BOJ 1987 알파벳

문제출저

풀이

DFS + 백트래킹 문제
일반적인 DFS 문제는 다음에 방문할 정점의 방문여부를 확인해야하는데 이문제는 방문여부 + 지금까지 지나온 알파벳 여부도 확인해주어야 한다.
상, 하, 좌, 우로 다음에 방문할 수 있는 곳이 있는지 확인하여 방문할때마다 깊이(depth)를 증가시켜주면서 지나갈 수 있는 ‘최대’칸인지 아닌지를 확인해주었다.
주의할점은 상, 화, 좌, 우 중 한 방향을 한번 DFS로 탐색하고 그 다음 방향으로 탐색을 진행할 경우 이전의 탐색했던 흔적들을 다시 리셋시켜주어야한다는것이다.

소스코드

전체소스

말이 움직임을 DFS로 확인하기

	public void moveHorse(Pos pos, boolean[][] visited, boolean[] alphaChk, int depth) {
		maxCnt = Math.max(depth, maxCnt);
		for (int d = 0; d < DIR.length; d++) {
			int nextY = pos.getY() + DIR[d][0];
			int nextX = pos.getX() + DIR[d][1];
			if (isAccessible(nextY, nextX) && !visited[nextY][nextX] && !alphaChk[map[nextY][nextX]]) {
				visited[nextY][nextX] = true;
				alphaChk[map[nextY][nextX]] = true;
				moveHorse(new Pos(nextY, nextX), visited, alphaChk, depth + 1);
				alphaChk[map[nextY][nextX]] = false;
				visited[nextY][nextX] = false;
			}
		}
	}