문제

치즈

풀이

이문제에서 bfs는 반복횟수가 치즈가 하나도 남지 않을때까지 반복해주기 위해서 다음과같이 설정하겠다

while(cheese > 0) {
	// 한시간 전 치즈 개수
	oneHour = cheese;
	bfs();
    // 치즈가 모두 없어지는데 걸리는 시간
	count++;
}

조금 헷갈렸던게 공기랑 와닿지 않는 부분을 다른 외곽 부분과 어떻게 구별을 할지 생각을 했었는데, [0,0]인 외곽에는 치즈가 없고 가운데에만 위치하기 때문에, BFS가 작동될때 외곽위주로 점검되어 큐에서 map[x][y] = 0인 외곽부터 점검해 나가고 map[x][y] = 1을 발견하면 그 즉시 0으로 변경 후에, 치즈가 삭제 되었음을 저장하면된다

마지막에 전부 삭제되고 나서 1시간전에 치즈의 개수는 갱신되므로 해당 내용을 출력하면 되었다

private static void bfs() {
	visited = new boolean[a][b];
    Queue<int[]> q = new LinkedList<>();
    // 모든 부분을 검증하기 위해 시도
    q.add(new int[] {0, 0});
    while(!q.isEmpty()) {
    	int[] m = q.poll();
      	for (int i = 0; i < dx.length; i++) {
			int x = m[0] + dx[i];
            int y = m[1] + dy[i];
            
            // 가로 a 와 세로 b사 이에 존재하며 아직 녹지 않은 부분이있다면 방문
            if (x >= 0 && x < a && y >= 0 && y < b && !visited[x][y]) {
            	// 치즈 부분이 존재 하면
				if (map[x][y] == 1) {
                	map[x][y] = 0;
                    cheese--;
                } else { // 치즈가 없다면 테두리인 부분을 넣고 계속 검증 하겠다.
                	q.add(new int[] {x, y});
                }
            }
        }
    }
}

특히 큐 안에 넣어지는 것들은 외곽인 0인 부분들만 들어가게 됨을 주의해야 한다. 그렇기 때문에 저절로 공기와 맞닿는 부분들만 점검하게 된다.

전체 코드

전체 코드