반응형
11-15 01:35
- Today
- Total
Link
개발하는 고라니
[백준] 16973번 : 직사각형 탈출 본문
반응형
[BFS]
나는 입력으로 주어지는 지도를 저장할 때, int[ ][ ]가 아닌 boolean[ ][ ]에 저장했다. 이유는 추후 연산이 오래 걸릴 것을 감안해서이다. 아무래도 숫자 비교 연산보다 boolean 연산이 훨씬 빠르다고 생각했다.
어쨋든 N x M 직사각형 안에 H x W 크기의 직사각형이 하나 더 들어있는데, 벽을 피해서 가장 왼쪽 위의 꼭지점을 목적지로 이동하는 문제라고 파악했다. 매번 직사각형을 옮기며 모든 꼭지점에 벽이 있는지를 보는 것 보다, 직사각형의 테두리만 검사하면 된다.
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
색이 칠해진 곳을 직사각형의 테두리라고 보면, 내부는 신경쓸 필요 없다. 오직 테두리가 다음 상하좌우로 이동할 때 그 곳에 벽이 있는지, 범위가 벗어나진 않는지만 체크해서 BFS를 수행하면 된다.
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point{
int y, x, move;
public Point(int yy, int xx, int move){
y=yy;
x=xx;
this.move=move;
}
}
static int n, m, h, w;
static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
static boolean[][] map = new boolean[1001][1001];
static boolean[][] visit = new boolean[1001][1001];
static boolean isAnyWall(int upY, int upX, int downY, int downX){
for(int i=upX; i<=downX; i++)
if(!map[upY][i] || !map[downY][i]) return false;
for(int i=upY; i<=downY; i++)
if(!map[i][upX] || !map[i][downX]) return false;
return true;
}
static int BFS(int startY, int startX, int endY, int endX){
Queue<Point> Q = new LinkedList<>();
visit[startY][startX] = true;
Q.add(new Point(startY, startX, 0));
while(!Q.isEmpty()){
Point p = Q.poll();
//가장 왼쪽 위에 꼭지점 좌표
int y = p.y;
int x = p.x;
if(y == endY && x == endX)
return p.move;
//가장 오른쪽 아래 꼭지점 좌표
int by = y + h - 1;
int bx = x + w - 1;
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
int nBy = by+Y[a];
int nBx = bx+X[a];
//범위를 벗어나는지 check
if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;
if(nBy > n || nBx > m) continue;
//다음 이동할 곳에 벽이 있는지 check
if(!isAnyWall(ny, nx, nBy, nBx)) continue;
visit[ny][nx] = true;
Q.add(new Point(ny, nx, p.move + 1));
}
}
return -1;
}
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());
for(int i=1; i<=n; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<=m; j++){
if(Integer.parseInt(st.nextToken()) == 0)
map[i][j] = true;
}
}
st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int endY = Integer.parseInt(st.nextToken());
int endX = Integer.parseInt(st.nextToken());
System.out.println(BFS(y, x, endY, endX));
}
}
위 코드는 이동하는 방향이 어디든 위 아래 양옆 테두리를 모두 벽이 있는지 검사한 것이고,
아래 코드는 이동하는 방향에 대한 테두리만 벽이 있는지 검사한 코드인데,
결과를 보았을 때 시간과 메모리의 차이가 크게 나지 않았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point{
int y, x, move;
public Point(int yy, int xx, int move){
y=yy;
x=xx;
this.move=move;
}
}
static int n, m, h, w;
static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
static boolean[][] map = new boolean[1001][1001];
static boolean[][] visit = new boolean[1001][1001];
static boolean isAnyWall(int upY, int upX, int downY, int downX, int a){
/* for(int i=upX; i<=downX; i++)
if(!map[upY][i] || !map[downY][i]) return false;
for(int i=upY; i<=downY; i++)
if(!map[i][upX] || !map[i][downX]) return false;*/
if(a == 0){
for(int i=upX; i<=downX; i++)
if(!map[upY][i]) return false;
}
else if(a == 1){
for(int i=upX; i<=downX; i++)
if(!map[downY][i]) return false;
}
else if(a == 2){
for(int i=upY; i<=downY; i++)
if(!map[i][upX]) return false;
}
else{
for(int i=upY; i<=downY; i++)
if(!map[i][downX]) return false;
}
return true;
}
static int BFS(int startY, int startX, int endY, int endX){
Queue<Point> Q = new LinkedList<>();
visit[startY][startX] = true;
Q.add(new Point(startY, startX, 0));
while(!Q.isEmpty()){
Point p = Q.poll();
int y = p.y;
int x = p.x;
if(y == endY && x == endX)
return p.move;
int by = y + h - 1;
int bx = x + w - 1;
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
int nBy = by+Y[a];
int nBx = bx+X[a];
if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;
if(nBy > n || nBx > m) continue;
if(!isAnyWall(ny, nx, nBy, nBx)) continue;
visit[ny][nx] = true;
Q.add(new Point(ny, nx, p.move + 1));
}
}
return -1;
}
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());
for(int i=1; i<=n; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<=m; j++){
if(Integer.parseInt(st.nextToken()) == 0)
map[i][j] = true;
}
}
st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int endY = Integer.parseInt(st.nextToken());
int endX = Integer.parseInt(st.nextToken());
System.out.println(BFS(y, x, endY, endX));
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 11021번 : A + B - 7 (0) | 2021.04.28 |
---|---|
[백준] 16932번 : 모양 만들기 (0) | 2021.04.15 |
[백준] 14923번 : 미로 탈출 (0) | 2021.04.15 |
[백준] 18119번 : 단어 암기 (0) | 2021.04.09 |
[백준] 16947번 : 서울 지하철 2호선 (0) | 2021.04.08 |
Comments