BFS(백준 : 미로탐색-2178문제) 접근 방법

백준 : https://www.acmicpc.net/problem/2178

백준 2178번 문제

 

0. 선행 작업

  (1) BFS 공부 : https://min-99.tistory.com/27

  (2) 알고리즘 문제 뇌구조 변경 : https://min-99.tistory.com/26

 

1. 생각해보기

1) 아이디어

  (1) "최소한의 칸수" = "최단거리" = "BFS"(너비우선 탐색)로 풀어야 함.

  (2) BFS로 풀려면 기본적으로 Queue와 방문 배열이 필요로 함. 

 

 

2) 시간 복잡도

BFS의 시간 복잡도 O(V(정점의 개수) + E(간선수))

O(NM + 4NM) => N과 M의 최대값 100

= O( 5 * 100 * 100) => 5만번(1초에 1억연산이 가능하니까 OK)

=O(5NM) => 상수 제거 함으로

=빅오의 시간 복잡도는 O(NM)이 된다. 

 

3) 자료구조

- queue, visited 배열, 

- miro (미로를 담을 배열)

- n, m (입력값)

 

 

2. 직접 풀어보기

https://github.com/moonlight-duck/study-algorithms/pull/21

[민주] 백준 2178 미로 탐색 by min-99 · Pull Request #21 · moonlight-duck/study-algorithms

 

 

결과) 

 

4년전에 dfs 개념을 공부하지 않은채 머리를 쥐어짜내서 시도한 기록이 있다..ㅎ 거의 근접하기는 했지만 코드에 원초적인 문제가 있었다..ㅎ 어째든 그때보다 훨씬 성장해서 다행이다..