1046: 빠른 길 찾기

Link : judge.koreatech.ac.kr/problem.php?id=1046

---

1. 문제

• 새로 연구원으로 입사한 현서는 아직 교내 지리가 익숙하지 않습니다.
  현서를 위해 교내 지도가 주어질 때, 현재의 위치에서 목적지 까지 가는 가장 짧은 거리를 구하는 프로그램을 만들 어 주세요.

 

---

2. 문제의 조건

• 1 <= T <= 10
• 1 <= N, M <= 100

 

---

3. 문제 접근

• 시간 복잡도
  
  BFS를 이용해야합니다. 범위가 10 * 100 * 100 이라 생각보다는 크므로 queue를 이용해야합니다.
  list의 pop(0)등은 O(N)이 소요되기 때문에 queue의 que.get()은 O(1)이기 때문에 이용해야합니다.

 

• 아이디어
  
  해당 문제는 전형적인 BFS문제입니다. 이 문제를 DFS로 풀 수는 있겠지만, DFS로 해결 할 경우 도달한 위치의 거리가 정답이라고 할 수 없기 때문에 BFS를 이용하는 것이 효과적입니다.

 

---

4. 풀이 방법

• map에서 start 지점을 찾습니다.
• start 지점에서 BFS를 수행합니다.
• queue(FIFO) 에 현재의 x, y를 넣고 que의 size가 0이 될 떄까지 반복합니다. 이 때, distance인 거리도 같이 표시해야 합니다.
• 만약 현재 이동가능한 거리일 경우
  ##
  이동 가능한 부분만 que에 추가를 했음에도 불구하고 한번 더 비교 해야 하는 이유는
  **
  **
  일 경우 0,0 의 오른쪽(1,0), 아래(0,1) 지점과
  1 1의 왼쪽(1,0)과 위(0,1) 지점이 서로 출동하므로 갔던 지점을 가지 않기 위해 이동가능한 거리인지 체크합니다.
  ##
  현재의 위치가 도착지점이면 거리를 반환해줍니다.
  현재 위치를 기록합니다.
  
  만약 움직일 수 있는 범위이면 거리 + 1과 함께 que에 추가합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/137

 

---

 

cjw.git@gmail.com