16973번 : 직사각형 탈출 [Java]

https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

 

해결 방안

1. x좌표와 y좌표, 이동거리를 담은 Point와 x좌표와 y좌표를 담은 Wall을 만든다.

2. 배열을 입력받으며 1이면 Wall에 넣어 arrayList에 저장한다.

3. bfs를 통해 맵 범위 안이면서 방문하지 않았고 벽이 포함되지 않는다면 직사각형을 이동시킨다.

4. 원하는 지점에 도착했다면 이동거리를 답으로 저장한다.

 

주의할 점

행과 열이 1부터 시작해서 map크기를 키우려다가 입력받은 수에 바로 1을 뺐었는데, 범위 체크를 위한 함수에서 그걸 고려하지 않고 확인해서 계속 오답을 제출했다.. 위에서 쓴 코드 기억하면서 아래를 작성하자..

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static class Point {
		int x, y, cnt;

		Point(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}

	static class Wall {
		int x, y;

		Wall(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int N, M, H, W, sR, sC, fR, fC;
	static int[][] map;
	static Queue<Point> queue;
	static ArrayList<Wall> wall;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static boolean[][] visited;
	static int ans = 987654321;

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(input.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		visited = new boolean[N][M];
		wall = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(input.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					wall.add(new Wall(i, j));
				}
			}
		}

		st = new StringTokenizer(input.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;

		queue = new LinkedList<>();
		queue.add(new Point(sR, sC, 0));
		visited[sR][sC] = true;

		search();
		System.out.println(ans == 987654321 ? -1 : ans);
	}

	private static void search() {

		while (!queue.isEmpty()) {
			Point p = queue.poll();

			if (p.x == fR && p.y == fC) {
				ans = p.cnt;
				break;
			}

			for (int d = 0; d < 4; d++) {
				int nr = p.x + dr[d];
				int nc = p.y + dc[d];

				if (!isIn(nr, nc) || visited[nr][nc])
					continue;

				if (hasWall(nr, nc))
					continue;

				queue.add(new Point(nr, nc, p.cnt + 1));
				visited[nr][nc] = true;
			}
		}
	}

	private static boolean hasWall(int nr, int nc) {
		boolean flag = false;
		for (Wall w : wall) {
			if (w.x >= nr && w.x < nr + H && w.y >= nc && w.y < nc + W) {
				flag = true;
				break;
			}
		}
		return flag;
	}

	private static boolean isIn(int nr, int nc) {
		if (nr < 0 || nc < 0 || nr + H - 1 >= N || nc + W - 1 >= M)
			return false;
		return true;
	}
}