[Baekjoon] 28471_W키가 빠진 성원이

Silver I

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

---

< W키가 빠진 성원이 >

 

문제 풀이 

 

F에서부터 이동해서 갈 수 있는 곳을 찾는다. 단, 위쪽으로 1칸 이동하는 W키가 고장난 것이므로 F에서 이동할 때는 아래로 1칸 이동하는 것을 제외한다.

 

 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 _28471_ { // W키가 빠진 성원이
	static int dx[] = { -1, 0, 0, -1, 1, -1, 1 };
	static int dy[] = { 0, -1, 1, 1, 1, -1, -1 };
	static int n;
	static boolean visited[][];

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

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

		char arr[][] = new char[n][n];
		visited = new boolean[n][n];
		int x = 0, y = 0;

		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < n; j++) {
				arr[i][j] = str.charAt(j);
				if (arr[i][j] == 'F') {
					x = i;
					y = j;
					visited[x][y] = true;
				} else if (arr[i][j] == '#') {
					visited[i][j] = true;
				}
			}
		}

		System.out.println(bfs(x, y));
	}

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

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 7; i++) {
				int a = temp[0] + dx[i];
				int b = temp[1] + dy[i];

				if (a >= 0 && a < n && b >= 0 && b < n) {
					if (!visited[a][b]) {
						cnt += 1;
						visited[a][b] = true;
						queue.add(new int[] { a, b });
					}
				}
			}
		}
		return cnt;
	}
}

변수)
n : 게임판의 크기
arr : 게임판 정보
visited : 방문 여부
x, y : 목적지 좌표

 

게임판 크기 n을 입력받는다. 게임판 크기만큼 게임판의 정보를 입력받아 arr에 저장한다. 저장하면서 목적지 위치를 찾아 x, y 좌표에 저장하고, 이동할 수 없는 공간을 미리 찾아 visited 배열에 방문 표시를 한다. 목적지 좌표를 bfs함수의 매개변수로 넘겨준다. bfs함수 호출한 후 반환값을 정답으로 출력한다.

 

bfs(int x, int y)

Queue에 시작 좌표인 x, y 배열을 저장한다. 큐가 빌 때까지 반복하며 다음 과정을 반복한다.

 

1) queue poll

2) 아래로 1칸 이동하는 것을 제외한 7가지 방향으로 이동한다.

3) 이동한 값이 게임판 범위 안이며, 아직 방문하지 않은 곳이라면 방문 표시 및 cnt+1을 하고 queue에 저장한다.

 

최종 cnt를 반환한다.

---

---