[Baekjoon] 25416_빠른 숫자 탐색

Silver II

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

---

< 빠른 숫자 탐색 >

 

문제 풀이 

 

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 _25416_ { // 빠른 숫자 탐색
	static int arr[][], result;
	static boolean visited[][];
	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;

		arr = new int[5][5];
		visited = new boolean[5][5];
		result = -1;

		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < 5; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(bf.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		bfs(r, c);

		System.out.println(result);
	}

	private static void bfs(int r, int c) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { r, c, 0 });
		visited[r][c] = true;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];

				if (x >= 0 && x < 5 && y >= 0 && y < 5 && !visited[x][y] && arr[x][y] != -1) {
					if (arr[x][y] == 1) {
						result = temp[2] + 1;
						break;
					}
					visited[x][y] = true;
					queue.add(new int[] { x, y, temp[2] + 1 });
				}
			}
			if (result != -1)
				break;
		}
	}
}

 

Main

변수)
arr : 보드 정보 저장
visited : 방문 여부
result : 최소 이동 횟수
r, c : 학생의 현재 위치
queue : [x좌표, y좌표, 이동 횟수]

 

- 보드 정보 입력받아 저장

- 현재 위치 입력

- bfs 함수 호출

- 최소 이동 횟수 출력

 

bfs

- queue에 저장 [x, y, 이동 수]

- queue가 빌 때까지 반복

: 4가지 방향으로 이동하여 보드 범위 안이며 아직 방문하지 않았고 이동한 칸의 값이 -1이 아니라면 

: 만약 이동한 칸의 값이 1이라면 종료

: 방문 표시 및 queue에 추가

---

---