문제(출처: https://www.acmicpc.net/problem/6189)
< Munching >
문제 풀이
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 _6189_ { // Munching
static int R, C;
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());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new boolean[R][C];
int x = -1, y = -1, x2 = -1, y2 = -1;
for (int i = 0; i < R; i++) {
String str = bf.readLine();
for (int j = 0; j < C; j++) {
if (str.charAt(j) == '*') {
arr[i][j] = true;
} else if (str.charAt(j) == 'C') {
x = i;
y = j;
} else if (str.charAt(j) == 'B') {
x2 = i;
y2 = j;
}
}
}
System.out.println(bfs(x, y, x2, y2));
}
private static int bfs(int x, int y, int x2, int y2) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { x, y, 1 });
arr[x][y] = true;
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 < R && b >= 0 && b < C && !arr[a][b]) {
if (a == x2 && b == y2) {
return temp[2];
}
arr[a][b] = true;
queue.add(new int[] { a, b, temp[2] + 1 });
}
}
}
return -1;
}
}
변수)
R, C : 배열 크기
arr : 배열
dx, dy : 상하좌우
x, y, x2, y2 : C, B 위치
배열 크기 R, C를 입력받는다. 배열 값을 입력받으면서 바위인 경우 방문 여부를 true로 저장하고 C와 B인 경우 각 좌표를 x, y, x2, y2에 저장한다. bfs를 호출한 결괏값을 출력한다.
bfs (C위치, B위치)
Queue에 C위치인 x, y와 1을 추가한다. 시작 위치를 true로 저장하고 bfs 탐색을 시작한다. queue가 빌 때까지 다음 과정을 반복한다.
1) queue poll
2) 상하좌우 탐색하며 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 queue에 추가한다. 만약 이동한 위치가 B 위치라면 temp[2] 값을 반환하며 끝낸다.
'🌞Algorithm > 🔥Baekjoon' 카테고리의 다른 글
[Baekjoon] 6080_Bad Grass (0) | 2024.09.26 |
---|---|
[Baekjoon] 11448_Ga (1) | 2024.09.25 |
[Baekjoon] 15240_Paint bucket (0) | 2024.09.23 |
[Baekjoon] 4993_Red and Black (1) | 2024.09.13 |
[Baekjoon] 6031_Feeding Time (0) | 2024.09.12 |