[BOJ 25307] 백준 25307번 - 시루의 백화점 구경

		2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 풀이
A		[BOJ 25304] 영수증
B		[BOJ 25305] 커트라인
C		[BOJ 25306] 연속 XOR
D		[BOJ 25307] 시루의 백화점 구경
E		[BOJ 25308] 방사형 그래프

1. 문제

$25307$. 시루의 백화점 구경 (2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 D번)

백준 25307번 - 시루의 백화점 구경 (https://www.acmicpc.net/problem/25307)

2. 풀이

시루가 이동하지 못하는 칸은 기둥이 있는 칸과 마네킹과 거리가 $K$ 이하인 칸이다. 이를 미리 구해서 이동하지 못하는 칸을 전부 표시한다면, 시루의 시작 지점에서 bfs를 돌려 가장 먼저 만나는 의자의 거리를 구할 수 있고, 그것이 정답이 된다.

마네킹과 거리가 $K$ 이하인 칸들은 각 마네킹의 위치에서 bfs를 돌려서 찾아낼 수 있다. 따라서, 마네킹의 위치를 전부 queue에 집어넣고 bfs를 돌려 $visited$가 $K$ 이하인 곳들을 찾아낸다.

체력 소모를 최소화하므로, 가장 먼저 만나는 의자의 거리를 출력한다. 의자와 만나지 않는다면 -1을 출력한다.

3. 채점 결과

4. 회고

.

5. 코드