[Baekjoon] 4993_Red and Black

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

---

< Red and Black >

 

문제 풀이 

 

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;
import java.util.StringTokenizer;

public class _4993_ { // Red and Black
	static boolean arr[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bf.readLine());
		int w = -1, h = -1;

		while ((w = Integer.parseInt(st.nextToken())) != 0 && (h = Integer.parseInt(st.nextToken())) != 0) {
			arr = new boolean[h][w];
			int x = -1, y = -1;

			for (int i = 0; i < h; i++) {
				String str = bf.readLine();
				for (int j = 0; j < w; j++) {
					if (str.charAt(j) == '#') {
						arr[i][j] = true;
					} else if (str.charAt(j) == '@') {
						x = i;
						y = j;
					}
				}
			}
			result = 1;
			arr[x][y] = true;
			bfs(x, y);

			bw.write(result + "\n");
			st = new StringTokenizer(bf.readLine());
		}
		bw.flush();
	}

	private static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y });

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int a = temp[0] + dx[i];
				int b = temp[1] + dy[i];
				if (a >= 0 && a < arr.length && b >= 0 && b < arr[0].length && !arr[a][b]) {
					arr[a][b] = true;
					result += 1;
					queue.add(new int[] { a, b });
				}
			}
		}

	}

}

변수)
arr : 방문 여부
dx, dy : 상하좌우
result : 결과
w, h : 배열 크기
x, y : 시작 위치

 

w, h 값이 0, 0이 아닐 때까지 입력받는다. 배열 정보를 입력받아 #인 경우 방문처리한다. @인 경우 시작 위치이므로 값을 저장해 두고 bfs 함수를 호출한다. 최종 result를 출력한다.

 

bfs(int x, int y)

Queue에 배열 형태로 위치를 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 4방향으로 탐색 후 범위 안이고 아직 방문하지 않았다면 방문 후 queue에 추가   

 

---

---