9370번 - 미확인 도착지
인터넷에 있는 다른 해법이랑 조금 다르게 문제를 풀어보았지만, 33%에서 틀렸다고 나옵니다..
반례 물어보는 질문은 절대 안하려 했는데, 혼자 머리 싸매다가 몸이 너무 뜨거워져서 이렇게 도움을 받아보고 싶었습니다.
제 풀이는, 최단 경로를 구하는 과정에서 g와 h를 지난 최단 거리를 distance[i][1]에 1 값을 넣어줌으로써 마지막에 목적 후보지에 대해서 확인하려고 하였습니다.
저도 처음에 말씀하신 것처럼 접근했었는데, 최단 거리의 경로가 여러 개 있을 수도 있다는 사실을 잊었습니다...
아.. 그걸 생각 못했군요..
답변자님의 얘기 듣고, 22번줄의 코드를 if distance[i[0]][0]>=dis+i[1]: 로 바꾸었는데,
비록 시간초과가 되었긴 했지만 80% 정도까지는 채점이 되네요!
조금 더 생각해보겠습니다
댓글을 작성하려면 로그인해야 합니다.
hy30n80 2년 전
인터넷에 있는 다른 해법이랑 조금 다르게 문제를 풀어보았지만, 33%에서 틀렸다고 나옵니다..
반례 물어보는 질문은 절대 안하려 했는데, 혼자 머리 싸매다가 몸이 너무 뜨거워져서 이렇게 도움을 받아보고 싶었습니다.
제 풀이는, 최단 경로를 구하는 과정에서 g와 h를 지난 최단 거리를 distance[i][1]에 1 값을 넣어줌으로써 마지막에 목적 후보지에 대해서 확인하려고 하였습니다.