728x90
분류
그래프 이론, BFS(너비우선탐색)
링크
https://www.acmicpc.net/problem/18405
18405번: 경쟁적 전염
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치��
www.acmicpc.net
전형적인 2차원 배열에서의 확장 문제.
번호가 서로다른 바이러스들이 번호순, 시간순으로 영역을 넓힌다.
상->하->좌->우 순으로 번진다고 한다. 근데 확산방향의 순서는 큰 의미는 없는듯. 서로다른 바이러스간 간섭이 방향에 의해 달라지진 않기 때문에.
중요 포인트
시간 S가 "끝났을 때" X,Y 위치의 바이러스 값을 출력해야 하므로 시간 S가 끝난 순간 전염의 확산을 그만 둬야 한다.
바이러스는 번호의 오름차순 순으로 확산이 진행된다. 따라서 큐에 맨처음 추가 하기전, 바이러스의 순서대로 정렬한 뒤 Queue로 변환해야한다.
코드
'프로그래밍 > programmers&bj' 카테고리의 다른 글
| [python] 백준 18428번: 감시 피하기 (0) | 2020.09.09 |
|---|---|
| [python] 백준 14888번: 연산자 끼워넣기 (0) | 2020.09.09 |
| [python] 15686번: 치킨 배달 풀이 (0) | 2020.09.02 |
| [python] 백준 3190번: 뱀 (0) | 2020.09.01 |
| [python] 프로그래머스: 소수 찾기 (0) | 2020.08.26 |