BFS
-
[백준] 16933 벽 부수고 이동하기 3Problem Solving/Baekjoon Online Judge 2020. 3. 24. 12:57
[문제이해] 1. NxM 으로 표현되는 map이 있다. (0은 이동할 수 있는 공간이고, 1은 이동할 수 없는 벽이다.) 2. 당신은 (1,1)에서 (N,M)위치로 최단 경로로 이동 해야한다. 3. 이 문제에는 낮과 밤이 존재한다. 가장 처음에 이동할 때는 낮이고, 이동할 때마다 낮과 밤이 바뀐다. 4. 이동하지 않고 같은 칸에 머무를 수 있는데, 이때도 낮과 밤이 바뀐다. 3. map에서 벽을 만나면, 벽을 부술 수 있다. (벽은 최대 k개 만큼 부술 수 있다.) 4. 단, 벽은 아침에만 부술 수 있다. 5. map이 주어지고 N, M, k가 주어졌을 때 최단 경로를 구해내야 한다. [설계] 1. 최단경로를 구하는 문제이므로 BFS를 사용하여 구현한다. 2. BFS로 방문하는 정점의 정보는 4가지이다...