✓

태그:

CLASS 5 ESSENTIAL

이미 체크한 공의 위치는 다시 체크할 필요가 없죠…!!

풀이 비스무리한거 보기

보드에 빨간 공과 파란 공, 그리고 공이 빠져나올 수 있는 구멍이 있을 때 파란 공은 빼지 않고 빨간 공만 빠져나오게 하는 최소의 움직임 수를 구하는 문제입니다. 공을 움직이는 것은 어렵지 않지만 문제는 두 공이 겹칠 때가 문제입니다. 다른 사람들이 질문을 한 것을 보면 두 공이 겹치는 과정을 잘못 구현하여 틀리는 경우가 많았는데, 사실 겹치는 것을 구현할 필요가 없습니다. 서로 장애물 취급하고 파란 공 한 번, 빨간 공 한 번, 다시 파란 공 한 번 굴리면 겹치는 것을 해결하는 것과 같은 결과가 나옵니다. 그리고 최소 횟수라면 역시 BFS인데, 공을 지운 보드는 항상 고정이기 때문에 보드는 놔두고 빨간 공과 파란 공, 그리고 이동 횟수만을 사용해서 큐에 넣고 BFS를 돌리면 답을 쉽게 찾을 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-16 23:50:04

---