bsy1343   5년 전

문제에 게시된 예제, 질문게시판에 있는 반례등을 찾아서 넣어서 풀어봤을 땐

답이 다 맞는거 같은데, 어느부분에서 틀렸는지 모르겠네요.

최대한 인터넷에 나온 답안 안보고 풀라고 원래 제가 생각한 대로 풀긴 하는데 너무 부족한게 많은거 같습니다ㅠㅠ

백트레킹도 잘 못 이해해서 쓰는거같고..

다른 반례나, 잘못된 알고리즘 지적 부탁드립니다.


djm03178   5년 전

Direction의 내용물이 잘못됐습니다. 다시 한 번 잘 보세요.

bsy1343   5년 전

와... 저건 못봤네요!
일단은 고쳐서 제출해봤는데 오타 말고도 또 다른 잘못된 로직이 있는거같네요..ㅠㅠ

매번 질문에 답글 달아주셔서 감사합니다^^ 저번에도 큰 도움이 되었어요!

djm03178   5년 전

그 다음 틀린 것은, 백트래킹이기 때문에 한 번 방문한 좌표라도 탐색을 끝낼 때 Visited 역시 다시 false로 만들어줘야 한다는 것입니다. 안 그러면 다른 경로를 통해 현재 좌표에 다시 도달해서 더 좋은 결과를 얻을 수 있어도 Visited가 true이기 때문에 통과를 할 수 없게 됩니다.

그걸 고치면 이제 시간 초과를 받는데, list.contains는 현재까지 삽입된 원소들을 전부 탐색해야 하기 때문에 느립니다. 무조건 한 방에 알 수 있게 하는 방법을 생각해 보세요.

bsy1343   5년 전

결국 아스키코드로 받아서 int형 Map으로 담아서 boolean으로 체크해서 해결하였습니다.

String형 Map으로 중복체크를 contains를 제외하고 생각이 안나서.. 감사합니다~!

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