대피소까지의 거리
실버 I의견: 0
재난 대응 센터는 \(R \times C\) 크기의 도시 지도에 \(K\)개의 대피소를 설치했다. 지도의 각 칸은 이동 가능한 도로(\(.\))이거나 통과 불가능한 건물(\(\#\))이다. 대피소는 도로 위에 설치되며, 대피소 칸은 \(S\)로 표시된다.
시민들은 상하좌우로 인접한 칸으로 한 번씩 이동할 수 있고, 건물로는 이동할 수 없다. 각 도로 칸에서 가장 가까운 대피소까지의 최단 거리를 그 칸의 대피 거리라 한다.
도달 가능한 모든 도로 칸의 대피 거리 중 최댓값을 구하여라. 대피소에서 도달 가능한 도로 칸이 대피소 자신뿐이면 \(0\)을 출력한다.
- \(1 \le R, C \le 1\,000\)
- \(1 \le K \le R \times C\)
- 대피소는 반드시 도로 칸 위에 설치된다.
- 대피소가 아닌 도달 가능한 칸이 없을 수 있다.
첫째 줄에 행의 수 \(R\), 열의 수 \(C\), 대피소의 수 \(K\)가 공백으로 구분되어 주어진다.
다음 \(R\)개의 줄에 지도의 각 행이 주어진다. 각 행은 \(C\)개의 문자로 이루어지며 \(.\), \(\#\), \(S\) 중 하나이다.
도달 가능한 모든 도로 칸의 대피 거리 중 최댓값을 출력한다. 대피소 이외의 도달 가능한 칸이 없으면 \(0\)을 출력한다.
4 4 1
....
.##.
....
S...
6
대피소 \(S\)는 \((4, 1)\)에 위치한다. 가장 먼 도달 가능 칸은 \((1, 4)\)이고 거리는 \(5\)이다. 벽 \(\#\)은 이동 불가능한 칸이다.
3 3 2
S.S
...
...
3
두 대피소 \((1,1)\)과 \((1,3)\)에서 가장 먼 칸은 \((3,2)\)이며, 두 대피소로부터의 최소 거리가 \(3\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
대피소까지의 거리
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
대피소까지의 거리