문제 내용은 입력으로 5×5 형태의 데이터를 받고 이후 마지막으로 입력받는 내용이 시작 좌표가 되겠는데 여기서 시작해서 0은 의미 없고 1은 사과 -1은 이동할 수 없는 좌표다, 3번 안에 사과를 2개 이상 먹으면 1 아니면 0을 출력해주면 된다
슥슥 읽다가 놓칠 수 있는 점은, 이동한 뒤에는 이동한 영역으로 다시 되돌아갈 수 없다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int[][] arr = new int[5][5];
static boolean status;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 5; i++) {
String[] split = br.readLine().split(" ");
for (int j = 0; j < 5; j++) {
arr[i][j] = Integer.parseInt(split[j]);
}
}
int[] start = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
boolean[][] visited = new boolean[5][5];
dfs(start[0], start[1], visited, 0, 0);
if (status) {
System.out.println(1);
} else {
System.out.println(0);
}
}
public static void dfs(int i, int j, boolean[][] visited, int count, int apple) {
visited[i][j] = true;
if (arr[i][j] == 1) {
++apple;
}
if (count == 3) {
if (apple >= 2) {
status = true;
return;
}
}
if (i + 1 < 5) {
if (arr[i + 1][j] != -1 && !visited[i + 1][j]) {
dfs(i + 1, j, visited, count + 1, apple);
visited[i + 1][j] = false;
}
}
if (i - 1 > -1) {
if (arr[i - 1][j] != -1 && !visited[i - 1][j]) {
dfs(i - 1, j, visited, count + 1, apple);
visited[i - 1][j] = false;
}
}
if (j + 1 < 5) {
if (arr[i][j + 1] != -1 && !visited[i][j + 1]) {
dfs(i, j + 1, visited, count + 1, apple);
visited[i][j + 1] = false;
}
}
if (j - 1 > -1) {
if (arr[i][j - 1] != -1 && !visited[i][j - 1]) {
dfs(i, j - 1, visited, count + 1, apple);
visited[i][j - 1] = false;
}
}
}
}문제를 풀어보자면 int[][] 배열 안에 입력받은 5×5 데이터를 모두 넣어주고 DFS를 돌려주면 되는데 boolean 형태의 visited 배열을 같이 보내서, 이동한 위치마다 false를 true 처리해주면서, visited 배열이 true인 값은 진행하지 않게 로직을 짜 주면 이동한 경로를 -1로 바꾸는 것과 동일해진다
그리고 현재 위치에 사과가 있다면 +1을 해주고 이후에는 동서남북으로 이동할 수 있다면 한 칸씩 움직이면서 DFS를 계속 호출하는 식으로 진행해주되, dfs 이후 다시 visited 배열을 false로 돌려놔야 실패했을 경우 깔끔한 상태에서 다시 탐색을 진행할 수 있다.
이후 동서남북으로 계속 뒤져보면서 3번째 뒤져보는 순간 사과가 2개 이상이었다면 1을, 그렇지 않으면 0을 출력해주면 끝이다
Leave a Reply