[BOJ][Python] 백준 16973번 - 직사각형 탈출

문제 링크: https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

---

문제 풀이

너비 우선 탐색, 누적 합

 

BFS를 이용하는 건 그다지 어렵지 않다. 대부분의 BFS 문제처럼 직사각형의 왼쪽 가장자리를 기준으로 방문하지 않았다면 방문해주고 벽이라면 방문하지 않는 등 일반적인 문제랑 비슷하다. 하지만 직사각형 전체 중에 벽이 있다는 걸 확인하는건 어떻게 해야할까? 먼저 H*W번을 매번 방문할 때 마다 체크해준다? 딱봐도 시간 초과날게 뻔하다. 따라서 누적 합을 이용한다. 2차원 누적 합 문제는 백준에 있으니 이 문제를 꼭 풀고 이 문제를 푸는 것을 추천한다. 그 문제의 로직을 그대로 가져와도 문제가 되지 않는다. 2차원 누적 합을 이용해서 벽의 개수를 구한다. 그리고 직사각형의 가장 왼쪽 위를 (nx, ny)라 하면 오른쪽 가장자리는 (nx+w-1, ny+h-1)이므로 이 범위 안의 누적 합을 이용해 벽이 아예 없는 경우를 체크해주면 된다. O(1)이므로 시간 초과 없이 빠르게 훑어보기가 가능하다.

 

코드

 

참고 자료

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

11660번: 구간 합 구하기 5

2차원 배열의 누적 합 문제이니 풀지 않았거나 기억이 안난다면 먼저 풀어볼 것을 추천한다.