[Baekjoon] 9790_Elephant Show

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

---

< Elephant Show >

 

문제 풀이 

 

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 _9790_ { // Elephant Show
	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 a = -1, b = -1;
		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };
		while ((a = Integer.parseInt(st.nextToken())) != 0 && (b = Integer.parseInt(st.nextToken())) != 0) {
			boolean arr[][] = new boolean[b][a];
			int x = -1, y = -1;
			for (int i = 0; i < b; i++) {
				String str = bf.readLine();
				for (int j = 0; j < a; j++) {
					if (str.charAt(j) == '#') {
						arr[i][j] = true;
					} else if (str.charAt(j) == 'A') {
						x = i;
						y = j;
					}
				}
			}
			int answer = 1;
			Queue<int[]> queue = new LinkedList<>();
			queue.add(new int[] { x, y });
			arr[x][y] = true;
			while (!queue.isEmpty()) {
				int temp[] = queue.poll();
				for (int i = 0; i < 4; i++) {
					x = temp[0] + dx[i];
					y = temp[1] + dy[i];
					if (x >= 0 && x < b && y >= 0 && y < a && !arr[x][y]) {
						arr[x][y] = true;
						answer += 1;
						queue.add(new int[] { x, y });
					}
				}
			}
			bw.write(answer + "\n");
			st = new StringTokenizer(bf.readLine());
		}
		bw.flush();
	}
}

변수)
a, b : 배열 크기
dx, dy : 상하좌우
arr : 배열 정보
answer : 정답

 

배열 크기로 0,0을 입력받기 전까지 다음 과정을 반복한다.  

1) 배열 정보를 입력받으며 #인 경우 true로 저장하고 A인 경우 시작 위치를 저장한다.

2) answer을 1로 선언하고 bfs 탐색을 시작한다. 상하좌우를 탐색하며 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시, answer+1 및 queue에 추가한다. 

3) 최종 answer를 출력한다. 

---

---