성준이의 개발블로그 성준이의 개발블로그

문제 링크https://www.acmicpc.net/problem/2206아이디어 이 문제는 (1,1) 부터 (N,M) 까지 가는 최단 경로를 구하는 문제입니다.0은 이동할 수 있는 곳(길)이고, 1은 이동할 수 없는 곳(벽)입니다.여기까지만 하면 보편적인 bfs 문제라고 생각할 수 있는데, 이 문제는 벽을 1개 부술수 있는 기회가 주어집니다. 벽을 3개 세우는 문제에서 백트래킹을 사용해서 벽을 세우고 바이러스가 최소로 퍼지게 했기 때문에 처음에 백트래킹을 사용해서 벽을 하나씩 부셔가며 bfs를 돌려 했지만 입력이 1000씩 이였습니다.bfs의 시간 복잡도는 O(V + E)로 간선의 개수는 "1000 X 1000 = 100만" 이고 Edge의 개수는 "상하좌우 4방향 = 400만" 입니다. 총 500만인..