깊이/너비 우선 탐색(DFS/BFS) > 게임 맵 최단거리

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

프로그래머스

 

일단 console.log 로 지형을 파악해본다

 

자료구조가 배열이기 때문에 오른쪽으로 가는걸 먼저 체크하는게 일단 편해보임 

현재위치를 저장하고

if (오른쪽이 0일 경우) 바로 다음 배열의 동일 index를 체크 (아래로 감)

else 오른쪽이 1일 경우 오른쪽으로 한칸 이동한 현재위치를 저장 후 

다시 위의 조건문을 호출해야하니까 저 조건문은 while 문이 됨


while (현재위치가 5,5일때까지 수행) {

위의 볼드된 코드를 넣어준다

}


여기서 문제가 있음

5, 5로 도달하지 못하는 경우에 무한루프에 빠지게 되니까

안전장치가 필요

그건 나중에 처리하고


저 조건문을 보강해야함

오른쪽도 0이고 아래도 0인 경우엔 위로가거나 왼쪽으로 되돌아가야 함

그리고 벽의 끝에 도달한 경우 (현재위치의 가로축 세로축 값이 주어진 2차원 배열의 크기만큼 도달했을 경우)

아래로 가거나 오른쪽으로 가야함
`
그리고 만약 방문한적이 있다면 다시 재방문을 하면 안된다 (다시 왔던길을 돌아가는 것은 최단거리가 아니니까)


이제 다시 무한루프 안전장치를 생각해보면

왔던 곳을 재방문을 하게 될 경우가 생기면 그냥 루프문을 탈출한다면 문제가 생길까?

이제 이걸 코드로 작성