[백준] 1600번 말이 되고픈 원숭이 JAVA 풀이
나의 풀이
처음 풀었을 때는 depth와 remain을 각각의 static 변수로 선언하고, bfs 메서드 내에서 경우를 분기하여 더하고 빼고 확인하는 과정을 거쳤었다.
다만 그 풀이는 메모리 초과가 났다.
결국 이 문제의 요지는 visited에서 한칸씩 앞뒤로 움직이는 방문은 continue하되, 앞서나간 '말' 이동이 거친 경로에 있는 장소를 한칸씩 움직인 경로가 도착하면 그 방문은 continue하면 안된다는 것이다.
그렇게 하기 위해서는 visited 배열을 3차원인 visited[x][y][remain]
으로 선언해야한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 하나의 이동경로에 의한 좌표 x,y와 이동 횟수 depth, 남은 '말' 이동횟수 remain
class Point {
public int x;
public int y;
public int depth;
public int remain;
public Point(int x, int y, int depth, int remain) {
this.x = x;
this.y = y;
this.depth = depth;
this.remain = remain;
}
}
class Main {
static int k, row, col;
//이 문제에서 가장 중요한 부분
//단순히 그 좌표지점에 방문했었는지가 중요한게 아니라 그 방문지점에 remain이 같게 도착했느냐가 관건이다
static boolean[][][] visited;
static int[][] map;
static Queue<Point> q;
static int[] dx = {1,0,-1,0,2,2,1,1,-1,-1,-2,-2};
static int[] dy = {0,-1,0,1,1,-1,2,-2,2,-2,1,-1};
public static void main(String[] args) throws IOException {
//input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
col = Integer.parseInt(st.nextToken());
row = Integer.parseInt(st.nextToken());
visited = new boolean[row][col][31];
map = new int[row][col];
q = new LinkedList<>();
for (int i = 0; i < row; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map[i][j] = Integer.parseInt(st2.nextToken());
}
}
//logic
q.offer(new Point(0,0, 0, k));
int result = bfs();
//output
System.out.println(result);
}
public static int bfs() {
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Point po = q.poll();
int x = po.x;
int y = po.y;
int depth = po.depth;
int remain = po.remain;
// 범위 벗어난 경우
if (x < 0 || y < 0 || x >= row || y >= col) {
continue;
}
// 장애물 만난 경우
if (map[x][y] == 1) {
continue;
}
// 오른쪽 하단에 도착한 경우 depth 반환
if (x == row-1 && y == col-1) {
return depth;
}
// 이 지점에 들린게 문제가 아니라, 같은 remain을 가지고 들렸는지 체크
if (visited[x][y][remain]) {
continue;
}
// 방문 기록
visited[x][y][remain] = true;
// 한칸씩 움직이는 경우이므로 depth만 더해짐
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
q.offer(new Point(nx, ny, depth + 1, remain));
}
// '말' 이동 횟수가 0이면 continue
if (remain == 0) continue;
// '말' 이동 횟수가 남았으면 이동시키고 depth는 +1, remain은 -1
for (int j = 4; j < 12; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
q.offer(new Point(nx, ny, depth + 1, remain - 1));
}
}
}
return -1;
}
}
Author And Source
이 문제에 관하여([백준] 1600번 말이 되고픈 원숭이 JAVA 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hahahaa8642/백준-1600번-말이-되고픈-원숭이-JAVA-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)