지영이의블로그

백준 - 2206 벽부수고 이동하기 문제 0 이동가능 1이동불가능 (0,0)에서 (N-1, M-1)위치까지가는 최단경로를 구하라 (최단경로가 없으면 -1) 최단경로는 시작하는칸(0,0)과 끝나는칸(N-1, M-1)을 포함한다. (최소 2 이상임) 💥 한개의 1을 0으로 바꾸어 사용 가능함. 💥 최대 맵의 크기는 1000*1000 임 1,000,000 문제 해결 방법 찾기 1. N행 M열의 그래프에 최단경로를 구하기 위한 BFS를 돌린다면 시간복잡도는 얼마나 걸리는가? - 모든 정점은 N_M개 이고, 각 정점에 간선은 4개씩 있다. - 한번 지나간 정점은 표기를 해두어 여러번 지나가지 않도록 한다.(방문체크) - 모든 정점을 지나는 시간 + 모든 간선을 확인하는 시간 = N_M + 4_N_M 인데 상수배는..