[Baekjoon] 17198_Bucket Brigade

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

---

< Bucket Brigade >

 

문제 풀이 

 

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 _17198_ { // Bucket Brigade

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

		char arr[][] = new char[10][10];
		boolean visited[][] = new boolean[10][10];

		int x = 0, y = 0, x2 = 0, y2 = 0;
		for (int i = 0; i < 10; i++) {
			String str = bf.readLine();
			for (int j = 0; j < 10; j++) {
				arr[i][j] = str.charAt(j);
				if (arr[i][j] == 'B') {
					x = i;
					y = j;
				} else if (arr[i][j] == 'R') {
					visited[i][j] = true;
				} else if (arr[i][j] == 'L') {
					x2 = i;
					y2 = j;
				}
			}
		}

		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y, 0 });
		visited[x][y] = true;

		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };
		boolean flag = false;
		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 < 10 && b >= 0 && b < 10 && !visited[a][b]) {
					if (a == x2 && b == y2) {
						System.out.println(temp[2]);
						flag = true;
						break;
					}
					visited[a][b] = true;
					queue.add(new int[] { a, b, temp[2] + 1 });
				}
			}
			if (flag) {
				break;
			}
		}
	}
}

변수)
x, y : B 위치
x2, y2 : L 위치
arr : 정보
queue : Queue
visited : 방문 여부

 

정보를 입력받는다. B위치와 L위치를 따로 저장하고 R 위치는 방문 처리를 한다. Queue에 B위치를 시작 위치로 저장하여 bfs 탐색을 한다. Queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 상하좌우 탐색 후 범위 안이며 아직 방문하지 않았다면 방문 표시 및 이동

3) 만약 L위치에 도달했다면 횟수 출력 후 종료

 

---

---