알고리즘19-2

Event Queue

박스를 큐로 생각하자.

 

이벤트 큐를 쓰는 문제를 먼저 하나 알아보자.

 

이렇게 시작하자

한 라운드에서 감염이 퍼져나간다. 상하좌우 중 2개에 감염이 있다면 나도 감염된다.

 

마지막에 감염이 되고 끝나는 상황을 그릴 수 있다.

round마다 전체를 보고 있으므로 round 개수 x n(세로) x m(가로)

(라운드 갯수는 상수가 아니기 때문에 커질 수 있다.)

 

이벤트 큐를 만들어둔다면?

큐에는 감염이 되어있는 칸들을 넣는다.

초기상태

첫번쨰 라운드에서 감염이 되는 칸때문에 추가로 감염이 되는 칸은 이렇게 4개 밖에 없다.

 

추가로 감염이 될 때마다 인접한 4개만 체크해보면 다음 라운드에 감염될 칸을 알 수 있다.

추가로 감염되는 칸은 큐에 들어간다.

(4개의 칸을 큐에 모두 넣는다고 하면 위와 같은 상황이 된다.?!)

 

큐에 모든 칸이 하나씩 들어가더라도 mxn개 밖에 들어가지 않는다.

nxm(처음에 전체 훑기) + nxmx5 = O(nxm) 15:30

---

 

traversal = search 라고도 부른다.

 

프림

 

 

다익스트라

 

A*

추정치를 통해..