[Baekjoon] 5958_Space Exploration

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

---

< Space Exploration >

 

문제 풀이 

 

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

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _5958_ { // Space Exploration
	static boolean arr[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

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

		int n = Integer.parseInt(bf.readLine());

		arr = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < n; j++) {
				if (str.charAt(j) == '.') {
					arr[i][j] = true;
				}
			}
		}

		int result = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!arr[i][j]) {
					arr[i][j] = true;
					result += 1;
					bfs(i, j);
				}
			}
		}
		System.out.println(result);
	}

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

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

변수)
arr : 방문 여부
dx, dy : 상하좌우
n : 배열 크기
result : 결과

 

n 값을 입력받는다. 정보를 입력받아 .인 경우 방문 처리한다. arr을 전체 탐색하며 아직 방문하지 않은 곳이라면 bfs를 호출한다. 최종 result를 출력한다.

 

bfs(int i, int j)

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

1) queue poll

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

 

 

---

---