1987번

백준 1987번: 알파벳(javascript, DFS, 백트래킹)

말이 지날 수 있는 최대의 칸 수를 구하는 문제이다. 최대의 칸을 구해야 하기 때문에 단순 BFS가 아닌 완전탐색 혹은 백트래킹을 이용해 문제를 풀어야 하겠다고 생각했다. 왜냐하면 DFS나 BFS는 한번 방문한 곳은 다시 방문하지 않는데 이 때문에 방문경로에 따라 최대값이 달라지는 경우가 생기기 때문이다. 백트래킹 풀이를 위해서 방문배열을 만들었는데 아스키코드를 이용해 방문을 체크하였다. 왜냐하면 Set자료형에 방문한 알파벳을 넣을수도 있지만 Set은 원소를 집어넣을 때 O(n)이 필요하지만 아스키코드를 이용해 배열의 인덱스에 바로 접근하면 O(1)로 시간복잡도를 줄일 수 있기 때문이다. 그리고 DFS의 인수로 cnt를 주어서 DFS가 재귀할 때마다 cnt에 1을 더해 최대값을 구하고자 했다. 이를 이용..