경쟁적 전염

바이러스 번호가 낮은 것부터 먼저 증식한다. 그렇기 때문에 바로 우선선위 큐를 써야겠다는 생각이 들었다.

• comparable을 구현한 클래스 정의⭐️⭐️⭐️⭐️⭐️

1. 시간이 같지 않은 경우 : 시간이 적은 것이 높은 우선순위.//BFS는 자동으로 시간(거리) 오름차순 탐색하는데 굳이 정렬기준을 만들어야하나? 추측) 바이러스 번호가 작은 것부터 전염이 일어난다고 했기 때문에 1번 바이러스부터 pq에 인접노드 넣을 때 해당 칸에 도달하기까지 걸린 시간도 함께 저장한다. => 바이러스 1번의 5초 걸린 좌표 << 바이러스 2번의 1초 거린 좌표 // 동일한 좌표에 대해 시간이 작은 걸로 우선순위 같는다? => 방문체크로 인해 동일한 좌표 2번 방문하지 않는다. 그렇다면 동일한 좌표는 아니고, 다른 좌표다.

2. 시간이 같은 경우 : 이 때만 바이러스 번호가 작은 것이 높은 우선순위 동시다발적으로 바이러스 확산이 일어난다.(?)1번 설명과 상이한 내용이다. 문제와 풀이 다시 보기. 따라서 바이러스 확산 위치가 공통되는 칸에 대해서는 바이러스 번호가 작은 것이 우선순위 갖도록 함!!!(1번 바이러스가 우선순위 가지므로 1번 바이러스가 방문하여 확산처리하고, 방문처리하여 재방문X)

3. 2번 케이스 확장) time도 함께 저장하는 이유 : 동시에 (x,y)에 도달한 경우에만! 바이러스 번호 작은 것이 높은 우선순위를 갖는다! 그렇지 않은 경우는 먼저 도달한 바이러스가 그 칸 차지한다! => 동시에 도달했다는 것은 그 칸에 도달하는 데 걸 time 값이 같다는 것이다. 그렇기 때문에 그 칸에 도달한 time을 기록하는 것이 필요하다! => 동시 도달했을 때만 바이러스 번호 작은 것이 우선순위 갖고, 그 외의 경우 BFS 특성으로 먼저 도달한 바이러스가 그 칸 차지하기 때문에(디폴트) comparable 구현할 때에도 time이 같은 경우만 구현하면 안 되나? => SSAP가능하다! if(this.time == o.time) {...} 이렇게만 구현하고 싶지만, else문도 함께 구현해야하기 때문에 원래 BFS 특성상 디폴트지만 else {this.time - o.time;}으로 시간 작은 순서로 정렬하게 처리해준다.

class Node impleements Comparable<Node> {
    int x,y,time,virus_num;
    //x,y : 좌표
    //time : 바이러스가 퍼질 때 걸리는 시간 : 작은 것이 우선순위 높음!
    //virus_num : 바이러스 번호 : 작은 것이 우선순위 높음!
    public int compareTo(Node o) {
        //1.시간이 같지 않은 경우 : 시간이 적은 것이 높은 우선순위!
        if(this.time<o.time || this.time > o.time) {
            return this.time - o.time;
        }
        //2.시간이 같은 경우 : 이때만! 바이러스 번호가 작은 것이 높은 우선순위!
        else {
            return this.virus_num - o.virus_num;
        }
    }
}

좀 더 직관적인 코드로 수정 :

class Node impleements Comparable<Node> {
    int x,y,time,virus_num;
    //x,y : 좌표
    //time : 바이러스가 퍼질 때 걸리는 시간 : 작은 것이 우선순위 높음!
    //virus_num : 바이러스 번호 : 작은 것이 우선순위 높음!
    @Override
		public int compareTo(Point o) {
			if(this.time == o.time) {//시간이 같을 때만! 바이러스번호가 작은 것부터 빼준다.
				return this.virus_num - o.virus_num;
			} else {
				return this.time - o.time;//원래 BFS 특성상 디폴트 같은데 else문이 꼭 있어야하니까 굳이 구현해줌...
			}
		}
}

코드 구조

1. 전역변수로 우선선위 큐(PQ), 방문 체크 배열 선언

2. main : 배열값 입력받을 때 값이 0이 아니면 PQ에 넣고 방문체크 해준다.

3. solve() : 큐가 비지 않을 동안 반복. while(!pq.isEmpty()){ Point cur = q.remove(); //1.불가능한 경우 : S를 초과하면 0을 출력(문제에서 주어진 대로) //2.정답 찾은 경우 : 우선순위 큐에서 뽑은 cur가 X,Y인지, Map[cur.x][cur.y]가 0이 아닌지 조건 검사 후 리턴 //3.BFS 탐색 ① 범위 체크 후 방문 체크. 방문 true로 마킹 ② pq에 다음 노드 삽입 : pq.add(nx,ny,cur.time+1, cur.virus_num) Point 객체 인스턴 생성할 때 현재 바이러스 번호로 넣어준다!⭐️⭐️⭐️⭐️⭐️ ③ Map[nx][ny]에 바로 현재의 바이러스 번호 마킹⭐️⭐️⭐️⭐️⭐️ => 큐에서 꺼낼때 재정의한 정렬 기준에 의해 시간이 적은 것, 시간이 같다면 바이러스 번호 작은 것이 자동으로 먼저 꺼내지기 때문에 바로 마킹하면 된다!