이번 문제는 백준의 골드 4 문제 알파벳이다.
보기엔 굉장히 단순한 문제인데.. 차근차근 읽어보자.
알파벳이 적힌 보드가 주어지고, 해당 보드를 탐색한다.
이 때 중복되는 알파벳은 밟을 수 없다.
최대 보드는 몇 칸 까지 밟을 수 있는가?
백트래킹
사실 보자마자 떠오른건 백트래킹이었다.
백트래킹으로 단순히 훑으며 중복되는 알파벳이 나오면 가지치기한다.
최대 보드크기도 20 X 20이라서 시간도 적당할 것 같았다.
하지만 아래의 코드를 제출했을 때, 시간초과를 받게 되었다.
void backtrack(int curr_x, int curr_y, int cnt) {
answer = max(answer, cnt);
for (int i = 0; i < 4; i++) {
int nx = curr_x + dx[i];
int ny = curr_y + dy[i];
if ((nx >= 0 && nx < row) && (ny >= 0 && ny < col)) {
if (!board_visit[nx][ny] && !alphabet_validator[board[nx][ny]]) {
board_visit[nx][ny] = true;
alphabet_validator[board[nx][ny]] = 1;
backtrack(nx, ny, cnt + 1);
board_visit[nx][ny] = false;
alphabet_validator[board[nx][ny]] = 0;
}
}
}
}뭔가 더 타이트한 조건으로 가지치기를 해야할 것 같다.
어떻게 시간을 줄일 수 있을까?
추가 조건 대신, 다른 자료구조
고민을 많이 해보다가 결국 다른 사람의 풀이를 참고했다.
딱히 추가적으로 걸 조건이 도저히 생각이 나지 않았다.
그런데 어이없게도 HashMap을 사용해서 시간이 초과된 것이다.
C++의 unordered_map은 정렬을 하지 않기 때문에,
삽입과 탐색이 모두 O(1)의 상수 시간 복잡도를 갖는 것으로 알고 있다.
하지만 왜 시간초과가 발생했을까..?
visit[] 1차원 배열을 선언해서 탐색하는 것과 시간은 같을 것 같은데,
한 번 알아봐야 할 것 같다.
아무튼, unordered_map 대신 1차원 배열을 사용해서 결국 통과했다.