BFS&Deque - Algospot, Hide_Seek3

문제 복기

모든 가중치가 동일하게 1일 때 BFS&큐를 이용하여 풀었다.

가중치가 0 또는 1인 경우에도 BFS를 이용하여 풀 수 있다. 그 비밀은 Deque 또는 2개의 큐 이용에 있다!

• 숨바꼭질3

1. 2개의 큐 이용 순간이동을 할 때는 시간이 0초가 걸리기 때문에 걸리는 시간에 영향을 주지 않고, +1/-1인 경우에만 1초가 걸린다. =>현재의 큐에 순간이동한 좌표 넣고, 그 이외의 경우 다음 큐에 넣는다. =>현재의 큐에 있는 정점들 다 순회하고 현재의 큐가 비면, 다음 큐가 현재 큐가 된다. 위의 과정을 반복한다!

2. Deque 이용 가중치가 0인 경우 Deque의 앞에 넣고, 가중치가 1인 경우 Deque의 뒤에 넣는다. Deque에서 정점을 뺄 때는 remove(=poll)을 해주고, 이것은 Deque의 앞에서부터 정점을 뺀다.

• 숨바꼭질3 - for문 구현! for문을 이렇게도 구현할 수 있구나! int 배열 변수명 없이 생성자로 바로 배열 생성하고, 원소 또한 변수로 생성!

for(int next : new int[] {cur*2,cur+1,cur-1})

for(int next : new int[] {cur*2,cur+1,cur-1}) {
				if(0<=next && next<MAX) {
					if(dist[next]  == -1) {
						if(next==cur*2) {
							dist[next] = dist[cur];
							dq.addFirst(next);
						} else {
							dist[next] = dist[cur]+1;
							dq.addLast(next);
						}
					}
				}
			}