[이론][완전탐색][BFS] Chapter 1

완전탐색의 세 번째 알고리즘 BFS 문제를 풀어보겠습니다.

---

토마토

문제의 정답은 여기에서 확인할 수 있습니다.

1. cin으로 입력받으면 200ms 걸리고, scanf로 받으면 100ms 걸립니다.
2. bfs를 시작할 때 1인 경우를 모두 queue에 넣고 bfs()를 진행하는 것이 핵심입니다.
3. 자잘한 조건을 효율적으로 맞춰주는 방법을 생각해봅니다.

벽 부수고 이동하기

문제의 정답은 여기에서 확인할 수 있습니다.

1. while(size–)를 통해서 dist구하기
2. bool visitied[x][y][2] : (x,y)를 방문하기까지 경로 중 벽을 부수고 왔는지 아닌지
3. while(size–)를 통해서 한 heigth씩 접근하기 때문에 visited된 경우는 가장 빨리 접근할 수 있는 경로로 온 것이 보장됨.

벽 부수고 이동하기2

문제의 정답은 여기에서 확인할 수 있습니다.

1. 위 문제에서 k를 입력받고 cb의 값을 고려해서 확장하면 됩니다.

벽 부수고 이동하기3

문제의 정답은 여기에서 확인할 수 있습니다.

1. 움직이지 않고 머무르는 것이 가능하다.
   1. 현재 밤이어서 벽을 부술 수 없는데, 하루 기다렸다가 부수고 지나가는 것이 더 빠른 경우를 고려해야 한다.
   2. 밤 && 다음이 벽 && 더 부술 수 있고 && 하루 추가했을 때 방문하지 않은 경우 -> 기다릴 수 있다.
   3. 낮 && 다음이 벽 %% 더 부술 수 있는 경우 -> 기다리지 않고 뿌신다.
   4. 다음이 벽이 아닌 경우에는 기다릴 필요가 없다.
2. 낮/밤 시스템이 도입된다. 벽은 낮에만 부술 수 있다. 첫 날이 낮이다.