문제풀이/백준oj
[백준OJ] 16973번 직사각형 탈출 - Java
https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 일반적으로 BFS를 이용하여 문제를 푸는데 주의해야할 것이 있습니다. 한 칸이 아닌 직사각형을 움직이기 때문에 직사각형 범위내에 1이 있는지를 확인해야하는데, 여까지 완전탐색을 진행한다면 Time Out이 날것입니다. 따라서 이 로직을 줄여야 하는데, 여기서 누적합을 이용하여 문제를 해결해주면 시간복잡도를 줄일 수 있습니다. 예를들어 0 0 0 0 0 0 0 1 0 ..
2022. 12. 31.
