문제 내용은 입력으로 배열을 받은 뒤 0,0 에서 시작해서 배열의 가장 끝까지 도달할 수 있으면 Yes 없으면 No를 출력해줘야 하는데 여기서 배열 간 이동 시에는 동쪽, 남쪽으로 1이 있을 경우에만 이동이 가능하고 0이 있다면 해당 방향으로는 움직일 수 없다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static String existPath = "No";
static boolean[][] visited;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
map = new int[arr[1]][arr[0]];
for (int i = 0; i < arr[1]; i++) {
int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < arr[0]; j++) {
map[i][j] = input[j];
}
}
visited = new boolean[arr[1]][arr[0]];
bfs(0, 0);
System.out.println(existPath);
}
public static void bfs(int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
visited[startX][startY] = true;
queue.add(new int[]{startX, startY});
while (!queue.isEmpty()) {
int[] xy = queue.poll();
int x = xy[0];
int y = xy[1];
if (x == map.length - 1 && y == map[0].length - 1) {
existPath = "Yes";
}
if (x + 1 < map.length) {
if (map[x + 1][y] == 1 && !visited[x + 1][y]) {
queue.add(new int[]{x + 1, y});
visited[x + 1][y] = true;
}
}
if (y + 1 < map[0].length) {
if (map[x][y + 1] == 1 && !visited[x][y + 1]) {
queue.add(new int[]{x, y + 1});
visited[x][y + 1] = true;
}
}
}
}
}
내 경우에는 BFS를 이용해서 문제를 풀었는데 Queue에 동쪽, 남쪽으로 이동할 수 있다면 큐에 담아주면서 이동하면서 끝까지 이동하는데 성공했다면 Yes를 끝까지 도달하지 못했다면 No를 출력해주면 끝이다.
Leave a Reply