[Baekjoon] 6229_Bronze Lilypad Pond

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

---

< Bronze Lilypad Pond >

 

문제 풀이 

 

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 _6229_ { // Bronze Lilypad Pond
	static boolean arr[][];
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int M1 = Integer.parseInt(st.nextToken());
		int M2 = Integer.parseInt(st.nextToken());
		arr = new boolean[M][N];
		int x1 = -1, x2 = -1, y1 = -1, y2 = -1;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if (num == 0 || num == 2) {
					arr[i][j] = true;
				} else if (num == 3) {
					x1 = i;
					y1 = j;
				} else if (num == 4) {
					x2 = i;
					y2 = j;
				}
			}
		}
		System.out.println(bfs(M1, M2, x1, x2, y1, y2));
	}
	private static int bfs(int m1, int m2, int x1, int x2, int y1, int y2) {
		int dx[] = { -m1, -m1, m1, m1, -m2, -m2, m2, m2 };
		int dy[] = { -m2, m2, -m2, m2, -m1, m1, -m1, m1 };
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x1, y1, 0 });
		arr[x1][y1] = true;
		int result = 0;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && !arr[x][y]) {
					if (x == x2 && y == y2) {
						return temp[2] + 1;
					}
					arr[x][y] = true;
					queue.add(new int[] { x, y, temp[2] + 1 });
				}
			}
		}
		return result;
	}
}

변수)
M, N, M1, M2 : 배열 크기, 이동 크기
arr : 배열
x1, y1, x2, y2 : 출발, 도착 위치

 

배열 크기와 이동 가능한 크기를 입력받는다. 배열 정보를 입력받으며 0,1이면 true로 저장하고 3이면 시작 위치를 저장, 4면 도착 위치를 저장한다. bfs를 호출한 결과를 출력한다.

 

bfs (이동 크기, 시작 좌표, 도착 좌표)

큐에 시작 좌표와 이동 횟수를 저장하고 시작 위치를 true로 저장한다. queue가 빌 때까지 다음 과정을 반복한다. 

1) queue poll

2) 8방향을 탐색하며 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 queue에 추가한다. 만약 이동 위치가 도착 위치라면 이동 횟수를 반환하고 종료한다.

---

---