Baekjoon 18405 경쟁적 전염 JAVA

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2018405

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 N*N크기의 map가 주어지고 바이러스를 퍼트리는데 S초 후 특정 위치의 값을 출력하는 문제다.

조건

바이러스는 작은 바이러스부터 퍼트리며 상하좌우로 똑같은 번호로 퍼트림

이미 바이러스가 있으면 해당 공간은 더이성 바이러스가 퍼지지 못함

 

처음에 문제를 보고는 시뮬처럼 풀면되겠다고 생각했고, 입력과 동시에 우선순위 큐에 바이러스를 담고,

무한 반복문을 돌려서 bfs를 통해 바이러스를 퍼트리고

시간을 증가시키고 시간이 같으면 멈추고 그렇지 않으면 이번에는 map를 체크해서

바이러스를 다시 큐에담는 방식으로 문제를 풀었더니 시간 초과가 발생했고, 이런저런 작업을 하다가

그냥 체크할필요없이 bfs하나만 돌리면 되겠다 생각해서 그렇게 해결했다.

 

먼저 우선순위큐에 넣을 데이터 형식으로 좌표값과, 바이러스 번호, 시간을 입력받고,

정렬에 대해서는 람다식으로  시간이 같으면 번호가 작은 순으로, 시간이 다르면 작은 시간으로 정렬하도록 하였고,

bfs를 돌면서 큐에서 뺀 거의 시간이 원하는 시간과 같으면 bfs를 멈추도록 했고

그렇지 않으면 이제 4방을 탐색해서 범위에 안 벗어나고 바이러스가 아니면 퍼트림과 동시에

큐에 넣어주는데 이때 시간을 1씩 증가시켜서 넣는 방식으로 문제를 해결했다.