6106 : DFS 응용 — 전염 시뮬레이션
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 격자 맵 정보와 시간 T가 주어집니다. 격자의 칸은 각각 건강한 상태 'S', 감염된 상태 'I', 벽 '#' 중 하나를 나타냅니다.
매 1초마다 감염자('I')와 인접한 상하좌우의 건강한 사람('S')은 감염 상태로 변하게 됩니다. 벽 '#'으로는 전염이 진행될 수 없습니다.
초기 감염자가 존재할 때, T시간이 흐른 뒤 감염된 총 사람(또는 칸)의 수를 구하는 프로그램을 작성하십시오. (초기 감염자 역시 결과에 포함됩니다.)
매 1초마다 감염자('I')와 인접한 상하좌우의 건강한 사람('S')은 감염 상태로 변하게 됩니다. 벽 '#'으로는 전염이 진행될 수 없습니다.
초기 감염자가 존재할 때, T시간이 흐른 뒤 감염된 총 사람(또는 칸)의 수를 구하는 프로그램을 작성하십시오. (초기 감염자 역시 결과에 포함됩니다.)
입력 설명
첫째 줄에 행 크기 N, 열 크기 M (1 ≤ N, M ≤ 50)과 경과 시간 T (0 ≤ T ≤ 100)가 공백 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 격자 맵 정보가 문자열 형태로 공백 없이 주어집니다.
둘째 줄부터 N개의 줄에 격자 맵 정보가 문자열 형태로 공백 없이 주어집니다.
출력 설명
T시간 후 감염된 칸의 총 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 1
SSS
SIS
SSS
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
각 격자 칸에 도달할 수 있는 최단 전염 시간을 기록하도록 방문 배열을 관리하고, DFS 탐색(혹은 BFS) 시 깊이가 T 이하인 칸들만을 방문하여 체크하면 전염 범위를 쉽게 알 수 있습니다.