문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.
이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
1 4 1
0010
예제 출력 1
5
예제 입력 2
1 4 1
0100
예제 출력 2
4
예제 입력 3
6 4 1
0100
1110
1000
0000
0111
0000
예제 출력 3
15
예제 입력 4
6 4 2
0100
1110
1000
0000
0111
0000
예제 출력 4
9
풀이
문제해석
0 0 1 0
낮밤^낮밤
출력 : 5
0 1 0 0
낮밤낮밤
출력 : 4
처음에는 문제 해석을 잘멋함
벽이 있는 전 좌표에서 밤인지 낮인지가 중요
import java.util.*;
class Pair {
int x, y, z, night;
Pair(int x, int y, int z, int night) {
this.x = x;
this.y = y;
this.z = z;
this.night = night;
}
}
public class Main {
public static int[] dx = {1, -1, 0, 0};
public static int[] dy = {0, 0, 1, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int l = sc.nextInt();
sc.nextLine();
int[][] a = new int[n][m];
int[][][][] d = new int[n][m][l+1][2];
for (int i=0; i<n; i++) {
String s = sc.nextLine();
for (int j=0; j<m; j++) {
a[i][j] = s.charAt(j) - '0';
}
}
d[0][0][0][0] = 1;
Queue<Pair> q = new LinkedList<Pair>();
q.offer(new Pair(0, 0, 0, 0));
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
int z = p.z;
int night = p.night;
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == 0 && d[nx][ny][z][1-night] == 0) {
d[nx][ny][z][1-night] = d[x][y][z][night] + 1;
q.offer(new Pair(nx, ny, z, 1-night));
}
if (night == 0 && z+1 <= l && a[nx][ny] == 1 && d[nx][ny][z+1][1-night] == 0) {
d[nx][ny][z+1][1-night] = d[x][y][z][night] + 1;
q.offer(new Pair(nx, ny, z+1, 1-night));
}
}
if (d[x][y][z][1-night] == 0) {
d[x][y][z][1-night] = d[x][y][z][night] + 1;
q.offer(new Pair(x, y, z, 1-night));
}
}
int ans = -1;
for (int j=0; j<2; j++) {
for (int i=0; i<=l; i++) {
if (d[n-1][m-1][i][j] == 0) continue;
if (ans == -1) {
ans = d[n-1][m-1][i][j];
} else if (ans > d[n-1][m-1][i][j]) {
ans = d[n-1][m-1][i][j];
}
}
}
System.out.println(ans);
}
}
결과는 시간초과
인강 코드 그대로 복붙해서 다시 해봤는데도 시간초과
어디를 줄여야할지 몰라서
마지막에 최소값을 출력할때 이중 for문이 였는데
좀더 간단하게 바꿈
결과는 성공인데
메모리는 703072KB 시간은 4844ms 너무 효율적이지 못하다.
좀더 시간을 줄여야겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair {
int x, y, z, v;
Pair(int x, int y, int z, int v) {
this.x = x;
this.y = y;
this.z = z;
this.v = v;
}
}
public class Main {
static int[][] graph;
public static final int[] dx = { 1, -1, 0, 0 };
public static final int[] dy = { 0, 0, 1, -1 };
static int N, M, K;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
N = Integer.parseInt(tokenizer.nextToken());
M = Integer.parseInt(tokenizer.nextToken());
K = Integer.parseInt(tokenizer.nextToken());
int[][][][] d = new int[N][M][K + 1][2];
graph = new int[N][M];
for (int i = 0; i < N; i++) {
String s = reader.readLine();
for (int j = 0; j < M; j++)
graph[i][j] = s.charAt(j) - '0';
}
d[0][0][0][0] = 1;
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(0, 0, 0, 0));
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
int z = p.z;
int v = p.v;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= M)
continue;
// 상하좌우가 빈칸이고 && 상하좌우에 방문을 안한경우
if (graph[nx][ny] == 0 && d[nx][ny][z][1 - v] == 0) {
d[nx][ny][z][1 - v] = d[x][y][z][v] + 1;
q.offer(new Pair(nx, ny, z, 1 - v));
}
// 벽을 한번도 안부슨 상황이고 상하좌우 벽이 있고 방문을 안한 경우
if (v == 0 && z != K && graph[nx][ny] == 1 && d[nx][ny][z + 1][1 - v] == 0) {
d[nx][ny][z + 1][1 - v] = d[x][y][z][v] + 1; // 벽을 부슨다. z+1
q.offer(new Pair(nx, ny, z + 1, 1 - v));
}
}
if (d[x][y][z][1 - v] == 0) {
d[x][y][z][1 - v] = d[x][y][z][v] + 1;
q.offer(new Pair(x, y, z, 1 - v));
}
}
int min = N * M + 2;
for (int i = 0; i <= K; i++) {
if (d[N - 1][M - 1][i][0] != 0)
min = Math.min(min, d[N - 1][M - 1][i][0]);
if (d[N - 1][M - 1][i][1] != 0)
min = Math.min(min, d[N - 1][M - 1][i][1]);
}
if (min == N * M + 2)
System.out.println(-1);
else
System.out.println(min);
}
}
