백준 18818, iguana instructions 코드/풀이 (이구아나 안내하기), Python, heapq/bfs 풀이

간만에 코테공부 ㅎㅎ 이거 실버1인데 두시간이나 걸렸당... 전에 분명 쉬웠던 유형중 하나가 bfs인데.. 공부좀 다시해야지

 

자세한 코드가 보고싶은 분은 깃허브 링크 눌러주세용

GitHub - Rhyankwon/algorithms

 

문제 설명 ㄱㄱ

18818번: Iguana Instructions

 

영어라 좀 어려워보이지만 풀어보면 글케 어려운 문제는 또 아닌 문제. 추천받아서 풀었는데, 예전같으면 쉽게 풀었을텐데 나도 오랜만에 푸는거라 그런지 두시간 가까이 걸렷다 ;;

 

#은 벽이고 .은 길이다. .만 따라서 출발지에서 도착지까지 가야하는데 (0, 0) -> (N-1, N-1) 그 과정에서 최소로 회전하는 경우에 몇번이나 회전하는지를 찾으면 된다.

 

개인적인 생각으로 이문제의 포인트는 이 부분이다.

while heap_list:
    start = heapq.heappop(heap_list)
    cnt, cur, ex_dir = start
    cx, cy = cur
    arr[cx][cy] = '#'
    if [cx, cy] == end_point:
        print(cnt)
        break
        # exit()

    for d in dir:
        dx, dy = d
        nx, ny = cx+dx, cy+dy
        n_cnt = cnt + [1, 0][ex_dir==d]
        if arr[nx][ny] != '#':
            heapq.heappush(heap_list, [n_cnt, [nx, ny], d])

내가 첫번째로 헷갈렸던 부분은 '#'표시를 어디에 할것인가..이다. 이게, 표시를 안 하면 뱅뱅도니까 표시를 안 할수는 절대 없는데.. 이미 표시가 돼있어버리면 마지막에 exit하기가 상당히 곤란해진다. 마지막 end에 도달할 때 방향을 바꿀수도 있고 그렇지 않을 수도 있는데 방향을 바꾸면 갑자기 count +1이 돼고 거기에서 끝나버려서 답이 실제로 가능할 수 있는 숫자보다 1이 커지게 된다.

 

그리고 답에 도달하면 그대로 끝내야 효율적으로 문제를 풀 수 있으니까, break를 안 할 수도 없는 노릇이다. 따라서 일단 어떤 지점에 갈 때 가능한 방향의 갯수를 모두 구한 뒤 거기에서 heap을 해서 그 중 가장 작은 갯수..이며 end point에 도달했을 때 답을 내는 방향으로 구현했다.

 

더 좋은 풀이가 있을수도?