suntouch   2년 전

안녕하세요.

1987번 문제가 Swift로 맞았습니다를 받은 사람이 없고 다 시간초과이신데요.

Swift로 맞았습니다를 받으려면 문제 자체의 시간제한을 늘려야 하는걸까요?

Swift가 그렇게 느린걸까요? ㅠㅠ

visited도 알파벳, 맵 두군데 다 체크하고 있는데...


제 소스가 틀린점이 없는거 같은데, 도움 주시면 감사드리겠습니다..!

wapas   2년 전

Swift로 풀어보니 불가능하진 않네요.

1. maxDepth을 board상에 있는 알파벳 종류 개수로 지정하세요. 

그러면 maxDepth = depth를 연산하는 시간을 줄일 수 있습니다. 또한, 최댓값이 26보다 작아지니 총 연산량도 줄어들겠죠.

2. board에 문자열 대신 숫자로 미리 저장해주세요. 

dfs 함수를 호출 할 때마다 'Int(board[ny][nx].asciiValue!) - 65'를 연산하는 시간을 줄일 수 있습니다.

3. 지나간 알파벳을 이미 방문 체크해줬기 때문에 mapVisited는 필요 없습니다.

4. 방문 체크는 Bool 배열 (visited) 대신 비트마스킹으로 해야 제한 시간 안에 해결됩니다. ( 비트마스크하는 변수를 전역 변수로 두지 않고 함수 인자로 받았습니다. )

저도 정확한 이유는 모르지만 Bool 배열에서 값을 조회하고 변경하는 것 보단 비트 연산하는 시간이 더 짧은 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.