[Baekjoon] 11448_Ga

문제(출처: https://www.acmicpc.net/problem/11448)

---

< Ga >

 

문제 풀이 

 

bfs를 사용하여 문제를 해결한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
public class _11448_ { // Ga
	static int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
	static int dy[] = { 0, 0, -1, 1, -1, 1, -1, 1 };
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(bf.readLine());
		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(bf.readLine());
			boolean arr[][] = new boolean[N][N];
			Queue<int[]> queue = new LinkedList<>();
			for (int j = 0; j < N; j++) {
				String str = bf.readLine();
				for (int k = 0; k < N; k++) {
					if (str.charAt(k) == 'b') {
						arr[j][k] = true;
					} else if (str.charAt(k) == 'w') {
						arr[j][k] = true;
						queue.add(new int[] { j, k });
					}
				}
			}
			bw.write(bfs(arr, queue) + "\n");
		}
		bw.flush();
	}
	private static int bfs(boolean[][] arr, Queue<int[]> queue) {
		int result = 0;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < N && y >= 0 && y < N && !arr[x][y]) {
					arr[x][y] = true;
					result += 1;
					queue.add(new int[] { x, y });
				}
			}
		}
		return result;
	}
}

변수)
dx, dy : 상, 하, 좌, 우, 대각선
T : 테스트 케이스 수
N : 배열 크기
arr : 배열
queue : 우선순위 큐 

 

테스트 케이스 수를 입력받는다. 테스트 케이스 수만큼 다음 과정을 반복한다.

1) 배열 크기를 입력받는다.

2) 배열 정보를 입력받으면서 b라면 true로 저장하고 w이면 true로 저장하면서 queue에 위치를 저장한다.

3) bfs를 호출한 결과를 출력한다.

 

bfs (배열, 큐)

result를 0으로 초기화한 후 queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 상, 하, 좌, 우, 대각선을 탐색하며 배열 범위 안이며 아직 방문하지 않은 곳이라면 result+1과 방문 표시 및 queue에 추가한다. 

result를 반환한다.

---

---