빠른 숫자 탐색
문제 정보
- 사이트 : 백준 알고리즘 사이트
- 문제 번호 : 25416
- 문제 분류 : bfs
- 난이도 : silver 2
문제 풀이
내가 짠 코드
생각한 문제 조건
1. 크기가 5,5인 map이 주어진다.
2. 학생의 위치가 r,c로 주어진다.
3. 1이 적혀있는 칸으로 가야한다.
4. 1에 도착할 수 있다면 최소 이동 횟수, 없다면 -1을 출력한다.
5. 학생은 상,하,좌,우로 이동가능하다.
6. 0,1로는 이동가능하고 -1로는 이동 불가능하다.
7. 최소 이동 칸이아닌 최소 이동 횟수를 출력한다.
💭 생각 노트
- 위치 값과 이동 칸 수를 담고 있는 Node Class 생성
- 최소 이동을 구해야 하므로 bfs를 사용한다.
- 기본 bfs 형태로 구현하면 될 것 같았다.
public class BJ_25416 {
static class Node {
int x;
int y;
int count;
public Node(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
static Queue<Node> q = new LinkedList<>();
static int[][] map;
static boolean[][] visit = new boolean[5][5];
static int[][] check = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static int bfs() {
while (!q.isEmpty()) {
Node node = q.poll();
for (int i = 0; i < 4; i++) {
int dx = node.x + check[i][0];
int dy = node.y + check[i][1];
if(0 <= dx && dx < 5 && 0 <= dy && dy < 5){
if(map[dx][dy] == 1){
return node.count + 1;
}
if(!visit[dx][dy] && map[dx][dy] == 0){
visit[dx][dy] = true;
q.add(new Node(dx, dy, node.count+1));
}
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
map = new int[5][5];
for (int i = 0; i < 5; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < 5; j++) {
map[i][j] = Integer.parseInt(input[j]);
}
}
String[] input = br.readLine().split(" ");
int x = Integer.parseInt(input[0]);
int y = Integer.parseInt(input[1]);
q.add(new Node(x, y, 0));
visit[x][y] = true;
System.out.println(bfs());
br.close();
}
}