문제
크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.
격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.
직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.
입력
첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다. 0은 빈 칸, 1은 벽이다.
마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.
격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.
출력
첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.
제한
- 2 ≤ N, M ≤ 1,000
- 1 ≤ H ≤ N
- 1 ≤ W ≤ M
- 1 ≤ Sr ≤ N-H+1
- 1 ≤ Sc ≤ M-W+1
- 1 ≤ Fr ≤ N-H+1
- 1 ≤ Fc ≤ M-W+1
- 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.
예제 입력 1
4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4예제 출력 1
7예제 입력 2
6 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
2 3 1 1 5 5예제 출력 2
8풀이
이 문제는 BFS 알고리즘을 이용해서 풀 수 있었다. 처음엔 벽 체크를 for문을 통해서 찾았는 데 시간이 오래걸려서 HashSet을 이용해서 벽을 체크했더니 시간을 줄일 수 있었다. 하지만 메모리는 증가했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static int M;
static int[][] map;
static HashSet<Pair> wall = new HashSet<>();
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int targetX;
static int targetY;
static int ans=-1;
static Iterator it;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
map = new int[N+1][M+1];
for(int i=1; i<=N; i++) {
input = br.readLine().split(" ");
for(int j=0; j<M; j++) {
map[i][j+1] = Integer.parseInt(input[j]);
if(map[i][j+1]==1)
wall.add(new Pair(i, j+1));
}
}
input = br.readLine().split(" ");
targetX = Integer.parseInt(input[4]);
targetY = Integer.parseInt(input[5]);
BFS(new Rect(Integer.parseInt(input[2]), Integer.parseInt(input[2])+Integer.parseInt(input[0])-1, Integer.parseInt(input[3]), Integer.parseInt(input[3])+Integer.parseInt(input[1])-1, 0));
System.out.println(ans);
}
public static void BFS(Rect rec) {
Queue<Rect> queue = new LinkedList<>();
boolean[][] visited = new boolean[N+1][M+1];
queue.add(rec);
visited[rec.x1][rec.y1] = true;
while(!queue.isEmpty()) {
Rect temp = queue.poll();
if(temp.x1==targetX && temp.y1==targetY) {
ans = temp.cnt;
break;
}
loop:for(int i=0; i<4; i++) {
int X1 = temp.x1+dx[i];
int X2 = temp.x2+dx[i];
int Y1 = temp.y1+dy[i];
int Y2 = temp.y2+dy[i];
if(X1<1 || X2>N || Y1<1 || Y2>M || visited[X1][Y1]) continue;
it = wall.iterator();
while(it.hasNext()) {
Pair p = (Pair)it.next();
if(p.x>=X1 && p.x<=X2 && p.y>=Y1 && p.y<=Y2)
continue loop;
}
visited[X1][Y1] = true;
queue.add(new Rect(X1, X2, Y1, Y2, temp.cnt+1));
}
}
}
public static class Rect {
int x1;
int x2;
int y1;
int y2;
int cnt;
public Rect(int x1, int x2, int y1, int y2, int cnt) {
this.x1=x1;
this.x2=x2;
this.y1=y1;
this.y2=y2;
this.cnt=cnt;
}
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
👶🏻Jr. Programmer