# 홈 방범 서비스

거리가 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하는 코드

```java
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로 시작한다.

```java
	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](/files/-Mkio6z438YG-dAWI3sT)

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

1. BFS 거리를 의미하는 **K를 증가시키는 타이밍** : 큐에 넣을 때 ❌ 큐에서 꺼낼 때⭕️\
   큐에 넣을 때마다 K를 증가시켜버리면 K는 1에서 시작하고 인접한 노드 갯수만큼 증가하게 된다. 이것은 K가 증가하는 올바른 양상이 아닐 뿐 더러,  운영 지출을 계산할 때 더 큰 값이 되어 오답이 되게 된다.
2. **이익, 지출로 손해계산 타이밍 : 큐 크기 반복만 끝나고 난 직후**
3. 엣지 케이스 : BFS를 하지 않은 것이 더 큰 값일 수 있기 때문에, BFS하기 전에 손해 계산 필요

```java
//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()){\
&#x20; int size = q.size();//현재 큐에 들어간 시작점 K에서 BFS\
&#x20; **K++;**\
&#x20; for(int i=0;i\<size;i++){\
&#x20;   for(int d=0;d<4;d++){...}&#x20;


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/swea/undefined-7.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.