일단.... 시간 내에 풀지 못한 문제..
아이디어는 생각했으나 준비해야 할 것이 있어서 그냥 포기하고 시험 종료함..
문제
You are given a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.
Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by H strings S1,S2,…,SH, each of length W. Specifically, the cell (i,j) is a start cell if the j-th character of Si is S, a goal cell if it is G, an empty cell if it is ., and an obstacle cell if it is #. It is guaranteed that there is exactly one start cell and exactly one goal cell.
You are currently on the start cell. Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in. However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)
Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.
More formally, check if there exists a sequence of cells (i1,j1),(i2,j2),…,(ik,jk) satisfying all of the following conditions. If such a sequence exists, find the minimum value of k−1.
- For every 1≤l≤k, it holds that 1≤il≤H and 1≤jl≤W, and (il,jl) is not an obstacle cell.
- (i1,j1) is the start cell.
- (ik,jk) is the goal cell.
- For every 1≤l≤k−1, ∣il−il+1∣+∣jl−jl+1∣=1.
- For every 1≤l≤k−2, if il≠il+1, then il+1=il+2.
시간초과 코드 (가지치기)
package week31;
import java.util.*;
public class Main {
static int H, W, answer = Integer.MAX_VALUE, sx, sy, gx, gy;
static char[][] map;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
public static void main(String[] args) {
init();
boolean[][] visit = new boolean[H][W];
visit[sx][sy] = true;
bfs(visit);
if (answer == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(answer);
}
private static void bfs(boolean[][] visit) {
Queue<CP> queue = new ArrayDeque<>();
queue.add(new CP(sx, sy, 0, 0, visit));
queue.add(new CP(sx, sy, 0, 1, visit));
while (!queue.isEmpty()) {
CP cur = queue.poll();
// System.out.println(cur.x+" "+cur.y);
if (cur.move > answer)
continue;
if (cur.x == gx && cur.y == gy) {
answer = Math.min(answer, cur.move);
return;
}
for (int d = 0; d < 4; d++) {
if (d % 2 != cur.dir)
continue;
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (!isOutOfBound(nx, ny) && !cur.visit[nx][ny] && map[nx][ny] != '#') {
boolean[][] nxtVisit = copyVisit(cur.visit);
nxtVisit[nx][ny] = true;
int nxtDir2 = cur.dir == 1 ? 0 : 1;
queue.add(new CP(nx, ny, cur.move + 1, nxtDir2, nxtVisit));
// System.out.println(nx+" "+ny+" "+cur.dir+" "+nxtDir2+"zzz");
}
}
}
}
private static boolean[][] copyVisit(boolean[][] visit) {
boolean[][] v = new boolean[H][W];
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < W; j++) {
v[i][j] = visit[i][j];
}
}
return v;
}
private static boolean isOutOfBound(int nx, int ny) {
if (nx < 0 || nx >= H || ny < 0 || ny >= W)
return true;
return false;
}
private static void init() {
Scanner sc = new Scanner(System.in);
H = sc.nextInt();
W = sc.nextInt();
map = new char[H][W];
for (int i = 0; i < map.length; i++) {
String s = sc.next();
for (int j = 0; j < W; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'S') {
sx = i;
sy = j;
}
if (map[i][j] == 'G') {
gx = i;
gy = j;
}
}
}
// for (int i = 0; i < map.length; i++) {
// System.out.println(Arrays.toString(map[i]));
// }
}
}
class CP {
int x;
int y;
int move;
int dir;
boolean[][] visit;
public CP(int x, int y, int move, int dir, boolean[][] visit) {
super();
this.x = x;
this.y = y;
this.move = move;
this.dir = dir;
this.visit = visit;
}
}
정답 코드(dp)
package week31;
import java.util.*;
public class Main {
static int H, W, answer = Integer.MAX_VALUE, sx, sy, gx, gy;
static char[][] map;
static int[][] dp;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
public static void main(String[] args) {
init();
int verti = bfs(0);
for (int i = 0; i < H; i++) {
Arrays.fill(dp[i], H*W+1);
}
dp[sx][sy] = 0;
int hori = bfs(1);
answer = Math.min(verti, hori);
if (answer == H*W+1)
System.out.println(-1);
else
System.out.println(answer);
}
private static int bfs(int dir) {
Queue<CP> queue = new ArrayDeque<>();
queue.add(new CP(sx, sy, dir));
while (!queue.isEmpty()) {
CP cur = queue.poll();
for (int d = 0; d < 4; d++) {
if (d % 2 != cur.dir)
continue;
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (!isOutOfBound(nx, ny) && map[nx][ny] != '#') {
if(dp[nx][ny] > dp[cur.x][cur.y] + 1) {
dp[nx][ny] = dp[cur.x][cur.y]+1;
int nxtDir = cur.dir == 1 ? 0 : 1;
queue.add(new CP(nx, ny, nxtDir));
}
}
}
}
return dp[gx][gy];
}
private static boolean isOutOfBound(int nx, int ny) {
if (nx < 0 || nx >= H || ny < 0 || ny >= W)
return true;
return false;
}
private static void init() {
Scanner sc = new Scanner(System.in);
H = sc.nextInt();
W = sc.nextInt();
map = new char[H][W];
for (int i = 0; i < map.length; i++) {
String s = sc.next();
for (int j = 0; j < W; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'S') {
sx = i;
sy = j;
}
if (map[i][j] == 'G') {
gx = i;
gy = j;
}
}
}
dp = new int[H][W];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], H*W+1);
}
dp[sx][sy] = 0;
sc.close();
}
}
class CP {
int x;
int y;
// int move;
int dir;
// boolean[][] visit;
public CP(int x, int y, int dir) {
super();
this.x = x;
this.y = y;
// this.move = move;
this.dir = dir;
// this.visit = visit;
}
}