문제 내용은 입력으로 가로 세로의 크기를 받고 이후 0, 1로 이루어진 문자열을 받은 뒤, 가장 상단에 있는 행의 값 중 0에서부터 시작해서 0을 타고 내려와 가장 아래 행의 0에 닿으면 YES 아니면 NO를 출력해주면 되겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int[][] map;
static boolean status;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] size = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
map = new int[size[0]][size[1]];
for (int i = 0; i < size[0]; i++) {
String s = br.readLine();
for (int j = 0; j < size[1]; j++) {
map[i][j] = s.charAt(j) - '0';
}
}
for (int i = 0; i < size[1]; i++) {
if (status) {
break;
}
if (map[0][i] == 0) {
boolean[][] visited = new boolean[size[0]][size[1]];
dfs(0, i, visited);
}
}
if (status) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
public static void dfs(int i, int j, boolean[][] visited) {
visited[i][j] = true;
if (i == map.length - 1 && map[i][j] == 0) {
status = true;
return;
}
// 동서남북
if (i + 1 < map.length) {
if (!visited[i + 1][j] && map[i + 1][j] != 1) {
dfs(i + 1, j, visited);
}
}
if (i - 1 > -1) {
if (!visited[i - 1][j] && map[i - 1][j] != 1) {
dfs(i - 1, j, visited);
}
}
if (j + 1 < map[0].length) {
if (!visited[i][j + 1] && map[i][j + 1] != 1) {
dfs(i, j + 1, visited);
}
}
if (j - 1 > -1) {
if (!visited[i][j - 1] && map[i][j - 1] != 1) {
dfs(i, j - 1, visited);
}
}
}
}
DFS를 이용해서 문제를 풀어주면 되는데, 다른 문제들과 비교해서 다른 점은 시작 위치가 가장 상단 행에서 0이면 모두 출발해볼 수 있고, 맨 위의 0과 맨 아래의 0이 몇개 연결되는지가 중요한게 아니기 때문에 단 하나라도 연결이 되면 이후에는 for문을 돌릴 필요 없이 바로 중단시키고 YES를 출력해주면 된다
가로 세로의 크기의 매우 크기 때문에, 다 돌려보다간 시간초과로 실패할 수 있기 때문이다.
Leave a Reply