[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스
📚 문제
BFS 문제이다.
이용자를 담는 배열을 만들어 서비스 영역마다 넣어준다.
위 그림을 보면 각 숫자에 사람이 있으면 카운팅 배열로 숫자 값에 1씩 더해준다.
넓혀지면서 1씩 늘어야하므로 BFS 탐색을 한다.
그리고 최종적으로 누적합을 면적 당 이용자의 총 인원을 구한다.
그리고 서비스를 제공함으로써 받는 비용과 운영 비용의 차이가 양수면서 서비스 면적이 가장 큰 경우 서비스를 받는 총 인원 수를 출력한다.
위 같은 작업을 모든 시작점에서 반복한다.
📒 코드
from collections import deque
def bfs(start_y, start_x): # BFS 탐색
queue = deque()
queue.append((start_y, start_x, 1)) # 시작점을 큐에 담는다, 서비스 영역도 담는다.
visited[start_y][start_x] = 1
k_arr[1] = arr[start_y][start_x]
while queue:
y, x, k = queue.popleft()
for i in range(4): # 네 방향 탐색
ny = y + dy[i]
nx = x + dx[i]
if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == 0:
visited[ny][nx] = visited[y][x]
k_arr[k + 1] += arr[ny][nx] # 집의 수를 더한다.
queue.append((ny, nx, k + 1)) # 서비스 영역을 넓혀서 큐에 담는다.
def house_max(): # 가장 많은 집을 서비스할 수 있는 경우를 찾는다.
global result
house_cnt = 0
for i in range(1, n * 2):
k = i
house_cnt += k_arr[i] # 누적합으로 적어준다.
if m * house_cnt - (k * k + (k - 1) * (k - 1)) >= 0: # 적자나지 않는 경우
result = max(result, house_cnt)
for tc in range(1, 1 + int(input())):
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
result = 0
dy = [0, 1, 0, -1] # 우 하 좌 상
dx = [1, 0, -1, 0]
for i in range(n): # 모든 좌표에서 시작한다.
for j in range(n):
k_arr = [0 for _ in range(n * 2)] # 서비스 영역의 크기별 집의 수
visited = [[0] * n for _ in range(n)] # 방문 여부 확인
bfs(i, j) # BFS 탐색
house_max() # 가장 많은 수의 집에 서비스할 수 있는 경우
print(f'#{tc} {result}')
🔍 결과
Author And Source
이 문제에 관하여([SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/SWEA-2117.-모의-SW-역량테스트-홈-방범-서비스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)