import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class B2178 {
static int N,M;
static int[][] Board;
static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; //상 하 좌 우
static boolean[][] visited;
static class Node{
int row, col, count;
Node(int r, int c, int ct){
row = r;
col = c;
count = ct;
}
}
public static int move(){
Queue<Node> queue = new LinkedList<>();
visited = new boolean[N][M];
visited[0][0] = true;
//지나야하는 칸수를 구하라고 했으니 count에 1을 넣어준다
queue.add(new Node(0,0,1));
while(!queue.isEmpty()){
Node temp = queue.remove();
if(temp.row==N-1&&temp.col==M-1){
return temp.count;
}
for(int i=0; i<4; i++){
// 현재 좌표에 상하좌우값을 각각 더해 검증
int rd = temp.row + D[i][0];
int cd = temp.col + D[i][1];
if(rd<0||rd>=N||cd<0||cd>=M) continue;
if(Board[rd][cd]==0) continue;
if(visited[rd][cd]) continue;
visited[rd][cd] = true;
queue.add(new Node(rd,cd,temp.count+1));
}
}
return -1;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
Board = new int[N][M];
String str;
//한줄로 숫자를 받아야 해서 string으로 받고 변환
for(int i=0; i<N; i++) {
str= sc.next();
for(int j=0; j<M; j++) {
Board[i][j]= Integer.parseInt(str.charAt(j)+"");
}
}
System.out.println(move());
}
}
이번문제는 지난번에 푼 최단거리 문제와 비슷해서 엄청 쉽게 풀었다
'연습문제 > JAVA' 카테고리의 다른 글
2331-반복수열 (0) | 2022.08.08 |
---|---|
10451-순열사이클 (0) | 2022.08.08 |
1620-DFS와 BFS (0) | 2022.08.06 |
16234-인구이동 (0) | 2022.08.05 |
16234-인구이동 (오답) (0) | 2022.08.04 |