목록1987 (1)

설모의 기록

[백준1987] 알파벳

이 문제는 DFS와 Backtracking을 이용해 중복되지 않은 알파벳은 방문하지 않는 조건으로 (0, 0) 에서 갈 수 있는 경로의 최대거리를 구하는 문제입니다. 저는 char 자료형 특징을 이용할 생각을 못하고 지금까지 지나온 알파벳을 ArrayList에 저장해 다음 경로로 갈 때마다 체크해주는 코드로 짜봤는데요. 시간이 8000ms가 넘길래 너무 놀라서 검색해봤는데 char 자료형을 이용하면 훨씬 수월하게 탐색할 수 있는 방법이 있었습니다. 아래에 비효율적으로 짠 코드와 최적화한 코드를 차례로 첨부하겠습니다. 우선 대문자 알파벳이기 때문에 'A' ~ 'Z' 까지가 범위가 되며 int형으로 바꾸면 65 ~ 90이 됩니다. 그래서 저는 check 배열의 인덱스를 (입력 알파벳 - 'A' ) 이라 생각..
알고리즘 2018. 5. 4. 17:25
이전 Prev 1 Next 다음