백준 2178. 미로찾기

문제

(1,1)부터 (N, M) 까지 가는 최소 칸의 수를 출력하는 문제이다.

- 미로 바깥으로는 나갈 수 없다.

- 0은 지뢰이므로 갈 수 없다.

 

 

문제 풀이

기존 코드

 

- 미로를 탐색하기 위해 bfs를 사용했으며 visited라는 배열을 선언하여 visited[x][y] 까지 가는 데 지나친 칸 수를 저장했다.

- 조건

  1. 미로를 넘어간 경우

  2. 지뢰인 경우 (map[x][y]가 0)

 

- 여기서 방문 여부에 따라 다른 로직을 작성하였다.

  - 방문 안한 경우 : 작업 큐(q)에 추가하고, visited[next_x][next_y]에  이전의 칸 수 +1 저장

  - 방문한 경우 : 새로운 길이 visited에 저장된 수보다 적은 경우, visited[next_x][next_y]에  이전의 칸 수 +1 로 업데이트

     ( 이유: 칸 수를 순회하다보면 2번째 방문했을 때 더 칸 수가 적은 경우가 있을 수 있다고 생각했음) (❌ 이 코드는 [수정] 부분에서 삭제)

 

수정 풀이

기존 코드는 방문 안한 경우와 방문한 경우로 나누었었다.

칸 수를 순회하다보면 2번째 방문했을 때 칸의 수가 더 적은 경우가 있을 수 있다고 생각했는 데, 나의 착각였음

⭐ bfs는 짧은 거리부터 순회하는 알고리즘으로 처음 방문한 칸이 이후 방문한 칸보다 무조건 적을 수 밖에 없다!

 

수정 후 코드

방문 안한 경우에만 작업 큐에 추가하고 visited를 갱신하는 방식으로 수정하여 코드가 더 간단해졌다.