홈 방범 서비스

거리가 K인 BFS 문제 풀이 접근 방식

틀린 부분

1. BFS할 때 k*k+(k-1)*(k-1) 조건 체크

   BFS 거리가 K까지 BFS하는 것이고, NxN의 모든 각 칸에서 BFS하면 된다. 각 칸에서 시작하는 BFS마다 BFS 거리를 의미하는 K는 1부터 시작하고, 범위를 벗어나면 BFS하지 않기 때문에 k*k+(k-1)*(k-1) 조건을 만족하는지 확인할 필요가 없다.

2. 다만 로직에 오차가 있다. 집의 위치에서 BFS 시작한다고 생각했는데, 전노드에서 거리가 K인 BFS를 완탐하면된다!

3. (틀리지는 않았지만 짚고 넘어가기) 손해 판단 : 이익-운영비용>=0 이면 손해가 아님. 이익-운영비용<0 : 손해.

현재 큐의 크기만큼 BFS하는 코드

while(!q.isEmpty()) {
			int size = q.size();
			K++;
			
			for(int i = 0 ; i < size ; ++i) {
				Node cur = q.poll();
				
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = cur.r + dir[d][0];
					int nc = cur.c + dir[d][1];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc]) continue;
					
					if(map[nr][nc] == 1) house++;
					
					q.offer(new Node(nr, nc));
					visited[nr][nc] = true;
				}
			}
			if(getOperationCost(K) <= house * M) {
				ans = house > ans ? house : ans;
			}
		}

정답 코드 K는 1부터 시작하고, 현재 집의 위치를 큐에 넣는다. while(!q.isEmpty()) 반복문과 상하좌우 4가지 방향 반복문 사이에 현재 큐의 크기만큼 반복문을 추가하여 현재 큐에 들어간 노드의 인접노드만 탐색한다.

집 갯수 카운팅 현재 Map[i][j] 이 0인지 1인지에 따라 Map[i][j]에서 시작한다. 큐에 (nx,ny) 넣고 방문체크하면서 Map값이 1인지 확인하여 바로 집 갯수 구할 수 있다!

아래 코드에서 K가 의미하는바는 현재 BFS 영역을 의미. BFS 시작위치에서 1부터 시작하기 때문에 K=1로 시작한다.

	private static void bfs(int r, int c) {
		q.offer(new Node(r, c));
		visited[r][c] = true;
		
		int K = 1;
		int house = map[r][c] == 1 ? 1 : 0;
		
		if(getOperationCost(K) <= house * M) {
			ans = K > ans ? K : ans;
		}
		
		while(!q.isEmpty()) {
			int size = q.size();
			K++;
			
			for(int i = 0 ; i < size ; ++i) {
				Node cur = q.poll();
				
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = cur.r + dir[d][0];
					int nc = cur.c + dir[d][1];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc]) continue;
					
					if(map[nr][nc] == 1) house++;
					
					q.offer(new Node(nr, nc));
					visited[nr][nc] = true;
				}
			}
			if(getOperationCost(K) <= house * M) {
				ans = house > ans ? house : ans;
			}
		}
	}

문제 정리 : 거리가 K인 BFS

서비스 영역은 BFS 거리가 K인 BFS 영역들을 의미한다. 따라서 모든 칸의 위치에서 BFS를 하면 된다. 범위를 벗어나면 BFS를 진행하지 않기 때문에 현재 노드에서 일반적인 BFS를 하면 된다.

이 때, 시작점을 넣은 큐. 큐의 크기(=1)만큼만 상하좌우 BFS한다. 1. 시작점(거리1) 기준 상하좌우(거리2) 2. 시작점(거리2) 기준 상하좌우(거리3) 2. 시작점(거리3) 기준 상하좌우(거리4)

현재 큐 크기만큼 반복하는 BFS

2번째 풀었을 때 틀린 이유(로직 흐름을 이해하자)

1. BFS 거리를 의미하는 K를 증가시키는 타이밍 : 큐에 넣을 때 ❌ 큐에서 꺼낼 때⭕️ 큐에 넣을 때마다 K를 증가시켜버리면 K는 1에서 시작하고 인접한 노드 갯수만큼 증가하게 된다. 이것은 K가 증가하는 올바른 양상이 아닐 뿐 더러, 운영 지출을 계산할 때 더 큰 값이 되어 오답이 되게 된다.

2. 이익, 지출로 손해계산 타이밍 : 큐 크기 반복만 끝나고 난 직후

3. 엣지 케이스 : BFS를 하지 않은 것이 더 큰 값일 수 있기 때문에, BFS하기 전에 손해 계산 필요

//k거리 BFS
int K=1;
//엣찌 케이스 : BFS를 하지 않은 것이 더 큰 값일수 있다!
if(getCost(K) <= house * M) {
			ans = K > ans ? K : ans;
}

현재 큐 크기만큼 반복하는 BFS 매커니즘 위의 그림에서 처럼 K=1부터 시작, 시작점(K)을 기준으로 BFS하고, BFS를 할 때, K는 1 증가하는 양상이다. 그렇기 때문에, 시작점(K=1,2,...)을 기준으로 BFS할 때, BFS 시작 전에 K를 증가 시켜주는 것이 적절하다.

코드상에서 로직 순서는 다음과 같다. while(!q.isEmpty()){ int size = q.size();//현재 큐에 들어간 시작점 K에서 BFS K++; for(int i=0;i<size;i++){ for(int d=0;d<4;d++){...}