https://www.acmicpc.net/problem/14620
풀이
- 모든 좌표 중 3개를 조합으로 고른다.
- 각 조합마다 꽃이 겹치지 않는지, 범위를 벗어나지 않는지 확인한다.
- 문제가 없다면 그 조합의 총 비용을 계산하고 최소값을 갱신한다.
| from itertools import combinations |
| |
| N = int(input()) |
| A = [list(map(int, input().split())) for _ in range(N)] |
- N은 격자 크기.
- A는 각 칸의 비용을 저장한 2차원 배열.
coordinates = [(i, j) for i in range(N) for j in range(N)]
| dr = [0, 0, 1, -1] |
| dc = [1, -1, 0, 0] |
| answer = 1e9 |
- 상하좌우 방향 설정.
- answer는 최소값 초기화.
for combination in combinations(coordinates, 3) :
| blossom = set() |
| bad = False |
| cost = 0 |
- blossom: 사용된 좌표 저장
- bad: 꽃이 겹치거나 격자 벗어나면 True
- cost: 현재 조합의 비용 합계
| for (r, c) in combination : |
| if (r, c) in blossom : |
| bad = True |
| blossom.add((r, c)) |
| cost += A[r][c] |
- 중심 위치 이미 사용됐으면 bad
- 비용에 중심 위치 추가
| for i in range(4) : |
| nr, nc = r + dr[i], c + dc[i] |
| if nr < 0 or N <= nr or nc < 0 or N <= nc : |
| bad = True |
| break |
| if (nr, nc) in blossom : |
| bad = True |
| break |
| blossom.add((nr, nc)) |
| cost += A[nr][nc] |
- 꽃잎 4방향을 탐색
- 범위 벗어나거나 겹치면 bad
- 안 겹치면 좌표를 blossom에 추가하고 비용 누적
| if not bad : |
| answer = min(answer, cost) |
코드
| |
| |
| |
| from itertools import combinations |
| |
| N = int(input()) |
| A = [list(map(int, input().split())) for _ in range(N)] |
| |
| coordinates = [(i, j) for i in range(N) for j in range(N)] |
| |
| dr = [0, 0, 1, -1] |
| dc = [1, -1, 0, 0] |
| answer = 1e9 |
| |
| for combination in combinations(coordinates, 3) : |
| blossom = set() |
| bad = False |
| cost = 0 |
| for (r, c) in combination : |
| if (r, c) in blossom : |
| bad = True |
| blossom.add((r, c)) |
| cost += A[r][c] |
| for i in range(4) : |
| nr, nc = r + dr[i], c + dc[i] |
| if nr < 0 or N <= nr or nc < 0 or N <= nc : |
| bad = True |
| break |
| if (nr, nc) in blossom : |
| bad = True |
| break |
| blossom.add((nr, nc)) |
| cost += A[nr][nc] |
| |
| if not bad : |
| answer = min(answer, cost) |
| |
| print(answer) |
댓글을 사용할 수 없습니다.