https://www.acmicpc.net/problem/16973
16973번: 직사각형 탈출
크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장
www.acmicpc.net
풀이
BFS를 사용해서 최소 이동 횟수를 구하면 된다. BFS를 수행할 때, checkWall() 메서드를 사용하여 직사각형이 이동할 위치에 벽이 있는지 체크한다.
주의할 점으로는, (1, 1)부터 시작하기 때문에 Sr, Sc, Fr, Fc를 저장할 때 -1을 해야 한다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int n, m, h, w;
static int sr, sc, fr, fc;
static int[][] map;
static int[] dr = {0, 0, 1, -1};
static int[] dc = {1, -1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
sr = Integer.parseInt(st.nextToken()) - 1;
sc = Integer.parseInt(st.nextToken()) - 1;
fr = Integer.parseInt(st.nextToken()) - 1;
fc = Integer.parseInt(st.nextToken()) - 1;
System.out.println(bfs());
}
static int bfs() {
Queue<int[]> q = new ArrayDeque<>();
boolean[][] visited = new boolean[n][m];
q.add(new int[]{sr, sc, 0});
visited[sr][sc] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0];
int c = cur[1];
int dist = cur[2];
if (r == fr && c == fc) {
return dist;
}
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr >= 0 && nr + h <= n && nc >= 0 && nc + w <= m && !visited[nr][nc] && checkWall(nr, nc)) {
q.add(new int[]{nr, nc, dist + 1});
visited[nr][nc] = true;
}
}
}
return -1;
}
// 직사각형이 이동할 위치에 벽이 있는지 체크한다.
static boolean checkWall(int r, int c) {
for (int i = r; i < r + h; i++) {
for (int j = c; j < c + w; j++) {
if (map[i][j] == 1) {
return false;
}
}
}
return true;
}
}
728x90
'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글
[백준] 1719번 : 택배(다익스트라) - 자바[Java] (0) | 2024.01.31 |
---|---|
[백준] 14940번 : 쉬운 최단거리 - 자바[Java] (0) | 2024.01.30 |
[백준] 17836번 : 공주님을 구해라! - 자바[Java] (1) | 2024.01.10 |
[백준] 16918번 : 봄버맨 - 자바[Java] (1) | 2024.01.08 |
[백준] 1283번 : 단축키 지정 - 자바[Java] (0) | 2024.01.07 |