-
반응형
https://www.acmicpc.net/problem/16973
풀이
일반적으로 BFS를 이용하여 문제를 푸는데 주의해야할 것이 있습니다.
한 칸이 아닌 직사각형을 움직이기 때문에 직사각형 범위내에 1이 있는지를 확인해야하는데, 여까지 완전탐색을 진행한다면 Time Out이 날것입니다.
따라서 이 로직을 줄여야 하는데, 여기서 누적합을 이용하여 문제를 해결해주면 시간복잡도를 줄일 수 있습니다.
예를들어
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
와 같이 있으면 누적합을 이용하여
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
로 누적합을 구해줍니다.
이런 뒤 , (2,2) ~ (3,4) 까지 벽이 있는지 확인해보기 위해서는 2번째 행에서 sum[2][4] - sum[2][1] = 2 가 되기때문에 벽이 있다고 판별할 수 있게됩니다. 이를 직사각형이 걸친 모든 행을 검사하며 BFS를 수행해줍니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int answer = Integer.MAX_VALUE; static int N, M, H, W, SR, SC, FR, FC; static int[][] maze; static int[][] sum; public static class Node { int x, y; public Node(int x, int y) { this.x = x; this.y = y; } } //누적합을 이용하여 벽이 있는지 검사 public static boolean containWall(int x, int y) { for (int i = x; i <= x + H - 1; i++) { if (sum[i][y + W - 1] - sum[i][y - 1] > 0) return true; } return false; } //갈 수 있는칸인지 검사 public static boolean isIn(int x, int y) { return (1 <= x && x + H - 1 <= N && 1 <= y && y + W - 1 <= M && !containWall(x, y)); } public static int bfs() { int[][] visited = new int[N + 1][M + 1]; int[][] mv = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; for (int i = 1; i <= N; i++) Arrays.fill(visited[i], Integer.MAX_VALUE); Queue<Node> q = new LinkedList<>(); q.offer(new Node(SR, SC)); visited[SR][SC] = 0; while (!q.isEmpty()) { Node node = q.poll(); int x = node.x; int y = node.y; int cost = visited[x][y]; if (x == FR && y == FC) { return cost; } for (int d = 0; d < 4; d++) { int nx = x + mv[d][0]; int ny = y + mv[d][1]; if (isIn(nx, ny) && visited[nx][ny] > cost + 1) { visited[nx][ny] = cost + 1; q.offer(new Node(nx, ny)); } } } 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.valueOf(st.nextToken()); M = Integer.valueOf(st.nextToken()); maze = new int[N + 1][M + 1]; sum = new int[N + 1][M + 1]; for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= M; j++) { maze[i][j] = Integer.valueOf(st.nextToken()); sum[i][j] = maze[i][j] + sum[i][j - 1]; } } st = new StringTokenizer(br.readLine()); H = Integer.valueOf(st.nextToken()); W = Integer.valueOf(st.nextToken()); SR = Integer.valueOf(st.nextToken()); SC = Integer.valueOf(st.nextToken()); FR = Integer.valueOf(st.nextToken()); FC = Integer.valueOf(st.nextToken()); System.out.println(bfs()); } }
반응형'문제풀이 > 백준oj' 카테고리의 다른 글
[백준OJ] 19542번 전단지 돌리기 - Java (0) 2023.01.02 [백준OJ] 2160번 그림 비교 - Java (0) 2023.01.02 [백준OJ] 16985번 Maaaaaaaaaze - Java (0) 2022.12.31 [백준OJ] 18511번 큰 수 구성하기 - Java (0) 2022.12.28 [백준OJ] 21943번 연산 최대로 - Java (0) 2022.12.28 댓글