3055번 - 탈출
물 > 고슴도치 > 물 > 고슴도치 bfs 에서 이해가 안되는 부분이 있습니다. 도움 부탁드려요
D.*
...
.S.
을 예로 들면
1번째 물 bfs를 돌리면
D1*
..1
.S.2번째 고슴도치를 돌리면
.11
1S1
까지는 이해가 되는데 그다음 물 bfs를 돌릴때
1행1열에 이미 1로 채워져 있으니 skip을 해버리던데 실제로 고슴도치가 2행1열에 있을수도 있고 2행2열에 있을수도있는데
저기를 물로 채워줘야 다음 물의 bfs일때 1행0열이 물로 잠길수있는걸 알 수 있지 않을까요?
도움 부탁드리겠습니다.
제가 이 문제를 풀지는 않았습니다만 생각해보면
(1,1)의 위치에서만 본다면 물이 고슴도치의 다음위치를 따라가는 형태가 될 겁니다. (둘의 속도는 같으므로)
결국 (1,1)의 위치에서 물이 퍼지는 것은 이미 고슴도치가 지나간 위치이므로 굳이 고려하지 않아도 고슴도치의 최소길이경로에 영향을 주지 않을 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
shfshfdl 4년 전
물 > 고슴도치 > 물 > 고슴도치 bfs 에서 이해가 안되는 부분이 있습니다. 도움 부탁드려요
D.*
...
.S.
을 예로 들면
1번째 물 bfs를 돌리면
D1*
..1
.S.
2번째 고슴도치를 돌리면
D1*
.11
1S1
까지는 이해가 되는데 그다음 물 bfs를 돌릴때
1행1열에 이미 1로 채워져 있으니 skip을 해버리던데 실제로 고슴도치가 2행1열에 있을수도 있고 2행2열에 있을수도있는데
저기를 물로 채워줘야 다음 물의 bfs일때 1행0열이 물로 잠길수있는걸 알 수 있지 않을까요?
도움 부탁드리겠습니다.