[SWEA] 2117. [シミュレーションソフトウェア機能テスト]ホーム防犯サービス
13391 ワード
📚 質問する
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%ED%99%88+%EB%B0%A9%EB%B2%94+%EC%84%9C%EB%B9%84%EC%8A%A4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
これは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}')
🔍 結果
Reference
この問題について([SWEA] 2117. [シミュレーションソフトウェア機能テスト]ホーム防犯サービス), 我々は、より多くの情報をここで見つけました https://velog.io/@yunhlim/SWEA-2117.-모의-SW-역량테스트-홈-방범-서비스テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol