👨💻 문제
크기가 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을 출력한다.
📖 예제
입력
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출력
7
✍️ 풀이
import java.io.*;
import java.util.*;
public class _16973 {
private static int boardHeight;
private static int boardWidth;
private static int rectHeight;
private static int rectWidth;
private static int startR;
private static int startC;
private static int destinationR;
private static int destinationC;
private static int[][] boardValue;
private static int[][] prefixBoardValue;
private static int compressedBoardHeight;
private static int compressedBoardWidth;
private static boolean[][] isWall;
private static boolean[][] isVisited;
private static Queue<int[]> q = new ArrayDeque<>();
private static int[] dr = {0,1,0,-1};
private static int[] dc = {1,0,-1,0};
public static void main(String[] args) throws IOException {
input();
setPrefixBoardValue();
compressBoard();
int result = bfs();
System.out.println(result);
}
private static void input() throws IOException {
...
}
private static void setPrefixBoardValue() {
...
}
private static void compressBoard() {
...
}
private static boolean isWall(int fromR, int fromC) {
...
}
private static int bfs() {
...
}
}
⌨️ 입력
private static int boardHeight;
private static int boardWidth;
private static int rectHeight;
private static int rectWidth;
private static int startR;
private static int startC;
private static int destinationR;
private static int destinationC;
private static int[][] boardValue;
위 변수값들을 입력받는다.
🧬 보드 배열 재구성
해당 문제는 미로 BFS와 유사하다.
다른 점이라면 보통 미로 BFS에서는 움직이는 말의 크기가 1x1인 데에 반해 해당 문제는 말의 크기가 별도로 정해진다는 것이다.
BFS를 돌 때마다 해당 말이 해당 보드의 위치에 자리 잡을 수 있을지 말의 크기만큼 확인해야 한다는 것이다.
이러한 확인은 큰 낭비를 야기할 수 있다.
누적합을 응용하여 말의 크기에 알맞게 보드를 미리 재구성하면 불필요한 연산을 최소화하고, 단순 미로 탈출 BFS로 문제를 해결할 수 있다.
기존 보드
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📌 누적합
private static void setPrefixBoardValue() {
prefixBoardValue = new int[boardHeight + 1][boardWidth + 1];
for (int r=1; r<boardHeight; r++) {
for (int c=1; c<=boardWidth; c++) {
prefixBoardValue[r][c] = boardValue[r-1][c-1] + prefixBoardValue[r][c-1];
}
}
for (int r=1; r<=boardHeight; r++) {
for (int c=0; c<=boardWidth; c++) {
prefixBoardValue[r][c] += prefixBoardValue[r-1][c];
}
}
}2차원 배열의 누적합은 헷갈리기 쉽다.
본인은 각 행들에 대한 누적합을 수행 후, 각 열들에 대한 누적합을 다시 수행하였다.
결과적으로 좌표 (r,c)가 주어졌을 때, (0,0)부터 (r,c)까지의 합을 배열로 저장하게 된다.
누적합을 수행한 배열
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 2
0 0 0 1 2 2 2 3
0 0 0 1 2 2 2 3이때, 가장 왼쪽의 열과 가장 위쪽의 행은 누적합을 위한 더미값이다. (0)
📌 지나갈 수 있는지 확인
private static boolean isWall(int fromR, int fromC) {
int untilR = fromR + rectHeight - 1;
int untilC = fromC + rectWidth - 1;
int value = prefixBoardValue[untilR+1][untilC+1] - prefixBoardValue[untilR+1][fromC] - prefixBoardValue[fromR][untilC+1] + prefixBoardValue[fromR][fromC];
return value > 0;
}누적합을 구했다면 해당 연산을 통해 해당 좌표에 사각형을 놓았을 때 해당 범위에 벽이 하나라도 있는지 확인할 수 있게 된다.
본래라면 사각형의 넓이만큼 탐색하며 벽을 확인해야 했다면, (width * height)
현재는 사각형의 넓이에 관계없이 연산 한 번에 벽을 확인할 수 있게 된다.
📌 재구성한 배열
private static void compressBoard() {
compressedBoardHeight = boardHeight - rectHeight + 1;
compressedBoardWidth = boardWidth - rectWidth + 1;
isWall = new boolean[compressedBoardHeight][compressedBoardWidth];
for (int r=0; r<compressedBoardHeight; r++) {
for (int c=0; c<compressedBoardWidth; c++) {
isWall[r][c] = isWall(r, c);
}
}
}위 연산을 통해 배열을 압축하게 되면,
더 이상 사각형의 넓이를 생각하지 않아도 되는 기본적인 미로 형태를 만들어내게 된다.
재구성된 배열
사각형의 높이 : 2
사각형의 너비 : 3
01110
01110
00001
11101
11100🐁 BFS
private static int bfs() {
isVisited = new boolean[compressedBoardHeight][compressedBoardWidth];
q.add(new int[] {startR, startC});
isVisited[startR][startC] = true;
int moveCount = 0;
while (!q.isEmpty()) {
int qSize = q.size();
for (int i=0; i<qSize; i++) {
int r = q.peek()[0];
int c = q.poll()[1];
System.out.printf("%d, %d, time: %d \n", r,c,moveCount);
if (r == destinationR && c == destinationC) {
return moveCount;
}
for (int dir=0; dir<4; dir++) {
int nextR = r + dr[dir];
int nextC = c + dc[dir];
if (nextR >= 0 && nextR < compressedBoardHeight && nextC >= 0 && nextC < compressedBoardWidth && !isVisited[nextR][nextC] && !isWall[nextR][nextC]) {
isVisited[nextR][nextC] = true;
q.add(new int[] {nextR, nextC});
}
}
}
moveCount++;
}
return -1;
}이제 단순히 목적지에 도달하는 BFS만 수행하면 답을 도출해낼 수 있다.
📄 전체 소스코드
import java.io.*;
import java.util.*;
public class Main {
private static int boardHeight;
private static int boardWidth;
private static int rectHeight;
private static int rectWidth;
private static int startR;
private static int startC;
private static int destinationR;
private static int destinationC;
private static int[][] boardValue;
private static int[][] prefixBoardValue;
private static int compressedBoardHeight;
private static int compressedBoardWidth;
private static boolean[][] isWall;
private static boolean[][] isVisited;
private static Queue<int[]> q = new ArrayDeque<>();
private static int[] dr = {0,1,0,-1};
private static int[] dc = {1,0,-1,0};
public static void main(String[] args) throws IOException {
input();
setPrefixBoardValue();
compressBoard();
int result = bfs();
System.out.println(result);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
boardHeight = Integer.parseInt(st.nextToken());
boardWidth = Integer.parseInt(st.nextToken());
boardValue = new int[boardHeight][boardWidth];
for (int r=0; r<boardHeight; r++) {
st = new StringTokenizer(br.readLine());
for (int c=0; c<boardWidth; c++) {
boardValue[r][c] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
rectHeight = Integer.parseInt(st.nextToken());
rectWidth= Integer.parseInt(st.nextToken());
startR = Integer.parseInt(st.nextToken()) - 1;
startC = Integer.parseInt(st.nextToken()) - 1;
destinationR = Integer.parseInt(st.nextToken()) - 1;
destinationC = Integer.parseInt(st.nextToken()) - 1;
}
private static void setPrefixBoardValue() {
prefixBoardValue = new int[boardHeight + 1][boardWidth + 1];
for (int r=1; r<boardHeight; r++) {
for (int c=1; c<=boardWidth; c++) {
prefixBoardValue[r][c] = boardValue[r-1][c-1] + prefixBoardValue[r][c-1];
}
}
for (int r=1; r<=boardHeight; r++) {
for (int c=0; c<=boardWidth; c++) {
prefixBoardValue[r][c] += prefixBoardValue[r-1][c];
}
}
// for (int r=0; r<=boardHeight; r++) {
// for (int c=0; c<=boardWidth; c++) {
// System.out.printf("%3d",prefixBoardValue[r][c]);
// }
// System.out.println();
// }
// System.out.println();
}
private static void compressBoard() {
compressedBoardHeight = boardHeight - rectHeight + 1;
compressedBoardWidth = boardWidth - rectWidth + 1;
isWall = new boolean[compressedBoardHeight][compressedBoardWidth];
for (int r=0; r<compressedBoardHeight; r++) {
for (int c=0; c<compressedBoardWidth; c++) {
isWall[r][c] = isWall(r, c);
// System.out.print(isWall[r][c] ? 1 : 0);
}
// System.out.println();
}
}
private static boolean isWall(int fromR, int fromC) {
int untilR = fromR + rectHeight - 1;
int untilC = fromC + rectWidth - 1;
int value = prefixBoardValue[untilR+1][untilC+1] - prefixBoardValue[untilR+1][fromC] - prefixBoardValue[fromR][untilC+1] + prefixBoardValue[fromR][fromC];
return value > 0;
}
private static int bfs() {
isVisited = new boolean[compressedBoardHeight][compressedBoardWidth];
q.add(new int[] {startR, startC});
isVisited[startR][startC] = true;
int moveCount = 0;
while (!q.isEmpty()) {
int qSize = q.size();
for (int i=0; i<qSize; i++) {
int r = q.peek()[0];
int c = q.poll()[1];
// System.out.printf("%d, %d, time: %d \n", r,c,moveCount);
if (r == destinationR && c == destinationC) {
return moveCount;
}
for (int dir=0; dir<4; dir++) {
int nextR = r + dr[dir];
int nextC = c + dc[dir];
if (nextR >= 0 && nextR < compressedBoardHeight && nextC >= 0 && nextC < compressedBoardWidth && !isVisited[nextR][nextC] && !isWall[nextR][nextC]) {
isVisited[nextR][nextC] = true;
q.add(new int[] {nextR, nextC});
}
}
}
moveCount++;
}
return -1;
}
}🤔 리팩토링
아래는 좌표를 Position이라는 클래스로 리팩토링한 코드이다.
이는 출발지 좌표, 목적지 좌표를 대체하였고,
BFS 수행 시, 기존에는 큐에 int[]을 넣은 반면 Position 클래스를 넣는다.
또한, 목적지에 도달했는지 확인하는 메소드를 equals 메소드를 통해 비교하여.
기존의 코드보다는 이해하기 쉬워졌지만, 메모리 및 속도를 더 많이 소모하게 되었다.
import java.io.*;
import java.util.*;
public class Main {
private static class Position {
private final int r;
private final int c;
public Position(int r, int c) {
this.r = r;
this.c = c;
}
public boolean equals(Position p) {
return r == p.r && c == p.c;
}
public boolean isTrue(boolean[][] arr) {
return arr[r][c];
}
public void setTrue(boolean[][] arr) {
arr[r][c] = true;
}
public Position getNewPosition(int dr, int dc) {
return new Position(r + dr, c + dc);
}
private boolean isOutOfIndex(int maxR, int maxC) {
return r < 0 || r >= maxR || c < 0 || c >= maxC;
}
}
private static int boardHeight;
private static int boardWidth;
private static int rectHeight;
private static int rectWidth;
private static Position start;
private static Position destination;
private static int[][] boardValue;
private static int[][] prefixBoardValue;
private static int compressedBoardHeight;
private static int compressedBoardWidth;
private static boolean[][] isWall;
private static boolean[][] isVisited;
private static Queue<Position> q = new ArrayDeque<>();
private static int[] dr = {0,1,0,-1};
private static int[] dc = {1,0,-1,0};
public static void main(String[] args) throws IOException {
input();
setPrefixBoardValue();
compressBoard();
int result = bfs();
System.out.println(result);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
boardHeight = Integer.parseInt(st.nextToken());
boardWidth = Integer.parseInt(st.nextToken());
boardValue = new int[boardHeight][boardWidth];
for (int r=0; r<boardHeight; r++) {
st = new StringTokenizer(br.readLine());
for (int c=0; c<boardWidth; c++) {
boardValue[r][c] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
rectHeight = Integer.parseInt(st.nextToken());
rectWidth= Integer.parseInt(st.nextToken());
int startR = Integer.parseInt(st.nextToken()) - 1;
int startC = Integer.parseInt(st.nextToken()) - 1;
int destinationR = Integer.parseInt(st.nextToken()) - 1;
int destinationC = Integer.parseInt(st.nextToken()) - 1;
start = new Position(startR, startC);
destination = new Position(destinationR, destinationC);
}
private static void setPrefixBoardValue() {
prefixBoardValue = new int[boardHeight + 1][boardWidth + 1];
for (int r=1; r<boardHeight; r++) {
for (int c=1; c<=boardWidth; c++) {
prefixBoardValue[r][c] = boardValue[r-1][c-1] + prefixBoardValue[r][c-1];
}
}
for (int r=1; r<=boardHeight; r++) {
for (int c=0; c<=boardWidth; c++) {
prefixBoardValue[r][c] += prefixBoardValue[r-1][c];
}
}
// for (int r=0; r<=boardHeight; r++) {
// for (int c=0; c<=boardWidth; c++) {
// System.out.printf("%3d",prefixBoardValue[r][c]);
// }
// System.out.println();
// }
// System.out.println();
}
private static void compressBoard() {
compressedBoardHeight = boardHeight - rectHeight + 1;
compressedBoardWidth = boardWidth - rectWidth + 1;
isWall = new boolean[compressedBoardHeight][compressedBoardWidth];
for (int r=0; r<compressedBoardHeight; r++) {
for (int c=0; c<compressedBoardWidth; c++) {
isWall[r][c] = isWall(r, c);
// System.out.print(isWall[r][c] ? 1 : 0);
}
// System.out.println();
}
}
private static boolean isWall(int fromR, int fromC) {
int untilR = fromR + rectHeight - 1;
int untilC = fromC + rectWidth - 1;
int value = prefixBoardValue[untilR+1][untilC+1] - prefixBoardValue[untilR+1][fromC] - prefixBoardValue[fromR][untilC+1] + prefixBoardValue[fromR][fromC];
return value > 0;
}
private static int bfs() {
isVisited = new boolean[compressedBoardHeight][compressedBoardWidth];
q.add(start);
start.setTrue(isVisited);
int moveCount = 0;
while (!q.isEmpty()) {
int qSize = q.size();
for (int i=0; i<qSize; i++) {
Position pos = q.poll();
if (pos.equals(destination)) {
return moveCount;
}
for (int dir=0; dir<4; dir++) {
Position newPos = pos.getNewPosition(dr[dir], dc[dir]);
if (!newPos.isOutOfIndex(compressedBoardHeight, compressedBoardWidth) && !newPos.isTrue(isVisited) && !newPos.isTrue(isWall)){
newPos.setTrue(isVisited);
q.add(newPos);
}
}
}
moveCount++;
}
return -1;
}
}
입니다.