[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)이므로 시간 초과 없이 빠르게 훑어보기가 가능하다.

 

코드

	from collections import deque
	import sys
	input = sys.stdin.readline
	n, m = map(int, input().split())
	a = []
	for _ in range(n):
	a.append(list(map(int, input().split())))
	h, w, sr, sc, fr, fc = map(int, input().split())
	visited = [[0 for _ in range(m+1)] for _ in range(n+1)]
	psum = [[0 for _ in range(m+1)] for _ in range(n+1)]
	for i in range(1, n+1):
	for j in range(1, m+1):
	psum[i][j] = psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+a[i-1][j-1]
	q = deque([(sr-1, sc-1)])
	visited[sr-1][sc-1] = 1
	dx = [1, -1, 0, 0]
	dy = [0, 0, 1, -1]
	while q:
	x, y = q.popleft()
	if x == fr-1 and y == fc-1:
	break
	for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	x1, y1 = nx+1, ny+1
	x2, y2 = x1+h-1, y1+w-1
	if (0 <= nx and 0 <= ny) and (nx+h <= n and ny+w <= m) and not (psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1]) > 0:
	if not visited[nx][ny]:
	q.append((nx, ny))
	visited[nx][ny] = visited[x][y] + 1
	print(visited[fr-1][fc-1] - 1)

view raw 16973.py hosted with ❤ by GitHub

 

참고 자료

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

11660번: 구간 합 구하기 5

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