[BOJ][골4][2206] 벽 부수고 이동하기

문제 링크

문제링크

첫 번째 풀이 : BFS

알고리즘

가장 기본적인 BFS를 진행합니다. 그리고 dp를 사용합니다.

• dp[x][y] : 현재까지 오는데 걸린 칸의 수
• dp[nx][ny] = dp[x][y]+1

int sz = q.size()를 사용해서 BFS의 깊이를 측정하는 것이 포인트입니다. 깊이를 측정함으로써 방문했던 곳을 다시 방문하지 않아도 됩니다. 한 번 방문한 곳은 더 이상의 최적 거리가 존재하지 않도록 하여 아래의 두 경우만 다음 좌표로 이동할 수 있습니다.

1. 다음이 0이고 방문하지않은 경우
2. 다음이 1이고 방문하지 않았고 더 부실 수 있는 경우

만약 int sz = q.size()를 사용하지 않으면 아래의 네 가지 경우를 고려해야 합니다. 훨씬 복잡하게 풀어야 합니다.

1. 다음이 0 && 미방문
2. 다음이 0 && 방문 && 더 짧아지는 경우
3. 다음이 1 && 미방문 && 더 부술 수 있음
4. 다음이 1 && 방문 && 더 부술 수 있음 && 더 짧아지는 경우

정답 코드

Success Notice: 수고하셨습니다.