문제 내용은 5×5 크기의 값을 받아서 지도로 사용해야 하는데, 6번째 입력으로 받은 두 값을 시작 위치로 한 뒤, 해당 위치에서 출발해서 1에 해당하는 사과 3개를 먹는 최소 이동 횟수를 구해야 한다.
만약 사과 3개를 구하지 못했다면 -1을 출력해주면 된다. 여기서 주의할 점은 지나온 길은 다시 되돌아갈 수 없고, -1의 경우에는 아예 지나갈 수 없다
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;
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 5; i++) {
int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.arraycopy(split, 0, arr[i], 0, 5);
}
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(ans);
} else {
System.out.println(-1);
}
}
public static void dfs(int i, int j, boolean[][] visited, int count, int apple) {
visited[i][j] = true;
if (arr[i][j] == 1) {
apple = apple + 1;
}
if (apple >= 3) {
status = true;
if (ans == 0) {
ans = count;
} else {
ans = Math.min(ans, count);
}
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;
}
}
}
}문제를 풀어보자면 2차원 배열에 입력받은 5줄을 모두 넣어준 후, DFS를 이용해 문제를 풀어줘야 하는데, 시작점은 마지막 입력받은 두 값을 가지고 배치해주면 되고, 시작점부터 동서남북으로 움직이되 사과 세 개를 찾으면 따로 boolean에 true 처리 해 주고 사과 값을 출력한 변수에 넣어주자.
처음 사과 세 개를 발견 시 무조건 넣어주면 되지만, 결국 최소 횟수를 출력해야 하기 때문에 이후부터는 Math.min을 사용해서 사과 3개를 모은 경우 중 횟수가 적은 경우를 저장해주면 된다.
모두 찾지 못했을 경우에는 따로 걱정할 필요가 없는게, 애초에 DFS 다 돌렸는데 구하지 못했으면 boolean 값이 변하지 않고 false로 남아 있었을 것이기 때문에 -1을 반환해주면 끝이다
Leave a Reply