[프로그래머스] 미로 탈출 명령어

문제보기

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

 

 

---

문제풀이

 

오랜만에 관련 코테를 풀어서 그런가 생각보다 오랜시간에 걸렸다.

 

기본적으로 dfs방식을 이용해 접근하고자 했다. 따라서 stack을 이용해 가능한 경로를 저장하고 알파벳 순서가 빠른 순으로 출력하도록 코드를 작성했고 시간초과가 발생했다ㅎ

 

해당문제가 다른 dfs 문제들과 다른 점이 있다면 크게 두 가지라고 생각한다.

1. 알파벳 순으로 빠른 길을 찾아야한다. dlru

2. 정해진 k만큼 이동해야한다.

3. 중간에 장애물(벽)이 없다. 즉 모든 dlru 모든 경로가 가능하다. (map을 벗어나지 않는 한도에서)

 

해당조건들을 통해 몇가지 조건을 찾을 수 있다.

먼저 장애물이 없기에 목표지점까지의 거리를 측정할 수 있다. 즉 앞으로 최소한 몇번을 옮겨야 목표지점까지 갈 수 있는 가를 계산할 수 있다. 따라서 dlru순으로 최대한 진행하면서 목표지점까지의 거리가 이동가능한 거리(k - 움직인 횟수)보다 조금 남도록 유지한다면, k번 안에 가장 작은 알파벳 조건으로 움직이는 길을 찾을 수 있다. 하지만 문제에서는 k번에 딱 맞춰 도착해야한다. 따라서 알파벳으로 가장 작도록 이동했음에도 k번을 만족하지 못했다면 du, lr, rl, ud와 같은 한 칸씩 반복 이동하는 방식을 반복해 해결할 수 있다. 이는 목표지점에 도착했을 때 남아있는 횟수가 짝수가 아니라면 k번에 맞추어 목표지점에 도착할 수 없다는 것을 의미한다.

 

 

필자는 dfs를 쓰지는 않았다. 굳이 stack에 가능한 경로들을 넣어줄 필요가 없었다. 단지 k번 이동하면서, 어떤 길을 선택해야하는 가 조건들을 추가했다. 해당 조건에는 위에서 말했다시피, dlru순으로 체크하면서 해당 방향으로 이동했을 때 남은 거리가 이동가능한 거리보다 큰가를 확인했다. 또한 목표지점에 도착했다면, 남은 이동거리가 짝수인가를 확인했다.

 

블로그 글을 쓰면서 생각한것인데, 굳이 반복문안에서 짝수여부를 확인할 필요가 없다. 맨 처음에 목표지점이 k보다 먼 곳에 있는 지, 만일 k보다 작다면 남은 횟수가 짝수인지를 확인하면 더 효율적인 코드가 될것이다.