백준 자석 체스[32334] 파이썬(Python) 코드 + 해설

백준 자석 체스 32334 문제

 

백준 자석 체스 문제는 Solved.ac 기준 실버 1 문제입니다.

1. 문제 해설

자석 체스에서 세종이는 마지막 자석을 보드에 놓으려고 한다. 자석을 놓았을 때 다른 자석들과 붙지 않으면 승리하고, 붙으면 붙은 자석들을 모두 가져가야 한다.

세종이가 이번 차례에 승리할 수 있는 위치를 찾고, 만약 없다면 가져가야 할 자석의 개수를 최소화하는 위치를 찾아야 한다.

2. 문제 해결 방법

1. 효율적인 접근 방법 선택
   • 보드의 크기가 최대 1000이므로, 모든 빈 칸에 대해 붙는 자석의 수를 계산해야 한다.
   • 각 빈 칸마다 주변에 있는 자석의 수를 효율적으로 계산하기 위해 2차원 누적 합(Prefix Sum)을 사용한다.
2. 자석의 붙는 조건 분석
   • 자석이 붙는 조건은 행과 열의 차이가 각각 D 이하인 경우이다.
   • 즉, 어떤 자석의 위치가 (r1​,c1​), 새로 놓을 자석의 위치가 (r2​,c2​)일 때, ∣r2−r1∣≤D그리고 ∣c2−c1∣≤D이면 자석이 붙는다.
3. 구현 단계
   • 보드 입력 및 빈 칸 위치 저장
     • 보드를 입력받으면서 빈 칸의 위치를 저장한다.
   • 2차원 누적 합 배열 생성
     • 자석의 위치 정보를 기반으로 누적 합 배열을 생성한다.
     • 누적 합 배열을 통해 특정 범위 내의 자석 개수를 빠르게 계산할 수 있다.
   • 각 빈 칸에 대한 처리
     • 각 빈 칸에 대해 거리 D 이내의 자석 수를 계산한다.
     • 누적 합 배열을 사용하여 (r−D,c−D)부터 (r+D,c+D)까지의 자석 수를 계산한다.
     • 만약 붙는 자석의 개수가 0이면 승리할 수 있는 위치로 기록한다.
     • 그렇지 않으면 붙는 자석의 개수가 최소인 위치를 갱신한다.
   • 결과 결정 및 출력
     • 승리할 수 있는 위치가 있으면 그 중 행 번호가 가장 작고, 열 번호가 가장 작은 위치를 출력한다.
     • 승리할 수 있는 위치가 없다면, 가져가야 할 자석의 개수가 최소인 위치를 동일한 방식으로 출력하고, 그 개수를 출력한다.

3. 백준 32334 자석 체스 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

N, D = map(int, input().split())
board = []
empty_cells = []

for r in range(N):
    row = list(map(int, input().split()))
    board.append(row)
    for c in range(N):
        if row[c] == 0:
            empty_cells.append((r, c))

# 누적 합 배열 생성
sum_board = [[0] * (N + 1) for _ in range(N + 1)]

for r in range(N):
    for c in range(N):
        sum_board[r + 1][c + 1] = sum_board[r + 1][c] + sum_board[r][c + 1] - sum_board[r][c] + board[r][c]

winning_positions = []
min_magnets = None
best_positions = []

for r2, c2 in empty_cells:
    # 붙는 자석의 범위 계산
    r1 = max(0, r2 - D)
    r3 = min(N - 1, r2 + D)
    c1 = max(0, c2 - D)
    c3 = min(N - 1, c2 + D)

    # 누적 합을 이용하여 붙는 자석의 수 계산
    total_magnets = sum_board[r3 + 1][c3 + 1] - sum_board[r1][c3 + 1] - sum_board[r3 + 1][c1] + sum_board[r1][c1]

    if total_magnets == 0:
        # 승리할 수 있는 위치
        winning_positions.append((r2, c2))
    else:
        # 붙는 자석의 수가 최소인 위치 찾기
        if min_magnets is None or total_magnets < min_magnets:
            min_magnets = total_magnets
            best_positions = [(r2, c2)]
        elif total_magnets == min_magnets:
            best_positions.append((r2, c2))

if winning_positions:
    # 승리할 수 있는 위치 중 가장 적합한 위치 선택
    winning_positions.sort()
    r_win, c_win = winning_positions[0]
    print(f"{r_win + 1} {c_win + 1}")
else:
    # 붙는 자석의 수가 최소인 위치 중 가장 적합한 위치 선택
    best_positions.sort()
    r_best, c_best = best_positions[0]
    print(f"{r_best + 1} {c_best + 1}")
    print(int(min_magnets))

4. 백준 32334 자석 체스 정답 코드 설명

1. 입력 처리 및 빈 칸 위치 저장
   • 보드를 입력받으면서 빈 칸의 위치를 empty_cells 리스트에 저장한다.
2. 2차원 누적 합 배열 생성
   • sum_board 배열을 만들어 (0,0)부터 (r,c)까지의 자석 개수를 저장한다.
   • 누적 합 배열을 통해 특정 범위 내의 자석 개수를 O(1)에 계산할 수 있다.
3. 각 빈 칸에 대한 처리
   • 각 빈 칸 (r2,c2)에 대해 붙는 자석의 범위를 계산한다.
     • 범위는 (max(0,r2−D),max(0,c2−D))부터 (min(N−1,r2+D),min(N−1,c2+D))까지이다.
   • 누적 합 배열을 사용하여 해당 범위 내의 자석 개수를 계산한다.
   • 붙는 자석의 개수가 0이면 winning_positions에 추가한다.
   • 그렇지 않으면 최소 붙는 자석의 개수를 갱신하며 best_positions에 추가한다.
4. 결과 결정 및 출력
   • 승리할 수 있는 위치가 있으면 winning_positions를 정렬하여 가장 우선순위가 높은 위치를 출력한다.
   • 승리할 수 있는 위치가 없으면 best_positions를 정렬하여 가장 우선순위가 높은 위치와 가져가야 할 자석의 개수를 출력한다.
   • 출력 시, 문제에서 요구하는 대로 행과 열 번호를 1부터 시작하도록 +1을 해준다.

5. 백준 32334 자석 체스 제출 결과

백준 32334 자석 체스 제출 결과

도움이 되셨다면 공감과 댓글 부탁드립니다