[Baekjoon] 29634_Hotel

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

---

< Hotel >

 

문제 풀이 

 

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

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class _29634_ { // Hotel
	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));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				if (str.charAt(j) == '*') {
					arr[i][j] = true;
				}
			}
		}
		int answer = -1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!arr[i][j]) {
					answer = Math.max(answer, bfs(i, j));
				}
			}
		}
		System.out.println(answer);
	}
	private static int bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y });
		arr[x][y] = true;
		int cnt = 1;
		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]) {
					cnt += 1;
					arr[a][b] = true;
					queue.add(new int[] { a, b });
				}
			}
		}
		return cnt;
	}
}

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

 

배열 크기를 입력받아 배열 크기만큼 배열 정보를 입력받는다. 값이 *라면 true로 저장한다. 배열을 전체 탐색하면서 아직 방문하지 않은 곳이라면 bfs를 호출한다. answer을 반환 값과 answer 값 중 최댓값으로 업데이트한다.

 

bfs (좌표)

큐에 좌표를 저장하고 시작 위치를 true로 저장한다. cnt를 1로 초기화한 후  queue가 빌 때까지 다음 과정을 반복한다. 

1) queue poll

2) 4방향을 탐색하며 배열 범위 안이고 아직 방문하지 않은 곳이라면 cnt+1과 방문 표시 및 queue에 추가한다. 

최종 cnt를 반환한다.

---

---