[Baekjoon]1987.알파벳

1987.알파벳

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

1987번: 알파벳

---

dfs + 백트래킹으로 풀었다. 말이 움직일 수 있는 최대 칸 수를 구하는 것이므로 dfs로 최댓값을 갱신하면서 풀었다. SWEA의 등산로 조성 문제도 비슷한 방식으로 풀었는데 이 문제는 그거보다 간단한 문제였다. 크게 다른 점은 이 문제에서는 방문 여부를 확인하기 위한 배열을 2차원으로 만들 필요가 없다는 것이다. 

 

위의 예시에서 좌상단에서 탐색을 시작하면 C를 방문했으므로 map에서 C인 지점은 앞으로 탐색할 필요가 없다. 그 다음 오른쪽으로 dfs를 오른쪽으로 먼저 시작했다고 가정하면 A를 방문하므로 다음 탐색에서 A인 지점 또한 탐색할 필요가 없다. 즉, 현재 지점의 상하좌우 위치에 대한 방문여부가 아니라 해당 위치에 알파벳에 대한 방문여부를 조사해야 한다. 따라서 알파벳 개수에 해당하는 26크기를 가지는 1차원 배열만 있으면 충분하다. 

 

A~Z 를 각각 0~25 로 생각하고 visited배열을 생성한다. 즉, A인 지점을 방문하면 visited[0]=true 로, C인 지점을 방문하면 visited[2]=true로 갱신하는 방식이다. 그리고 char타입을 int타입으로 변환하기 위해 -'A' 연산을 통해 해당 알파벳에 대한 인덱스 값을 매핑할 수 있도록 했다.  

private static void dfs(int curX, int curY) {

		int curIdx = map[curY][curX] - 'A';
		visited[curIdx] = true;
		step++;

		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i];
			int nextY = curY + dy[i];
			

			if (nextX >= 0 && nextY >= 0 && nextX < C && nextY < R) {
				int nextIdx = map[nextY][nextX] - 'A';
				
				if (!visited[nextIdx]) {
					dfs(nextX, nextY);
				}
			}
		}
		max = Math.max(max, step);

		step--;
		visited[curIdx] = false;
	}

<전체코드>