【백준】- 22151. Игра

문제

본 문제는 외국어 문제이기에, 제가 문제 번역을 작성해 두었습니다. 아래의 링크를 참고해 주세요!

https://www.acmicpc.net/board/view/101822

글 읽기 - 【지문 재작성】22151. 룬석 옮기기 게임

풀이

게임을 먼저 시작하는 알파가 이동 한 번으로 룬석을 정해진 위치로 옮길 수 있는지, 없는지에 따라 상황을 나누어서 생각해 봅시다. 이동 한 번으로 정해진 위치로 옮길 수 있는 경우라면, 거리가 $m$ 이하인 경우겠죠.

1. 한 번에 옮길 수 있는 경우

한 번에 정해진 위치로 옮길 수 있다면, 당연히 옮기는 것이 최선의 전략입니다. 게임은 알파가 항상 승리하게 됩니다.

2. 한 번에 옮길 수 없는 경우

한 번에 옮길 수 없는 경우라면, 알파가 룬석을 이동시킨 후 베타에게 차례를 넘겨 줘야 합니다.

 

여기서 알파가 거리가 정해진 위치와의 거리가 $m$ 이하인 지점으로 룬석을 이동시키면 어떻게 될까요? 베타가 차례를 넘겨받은 후 룬석을 정해진 위치로 옮길 수 있게 되므로 알파가 패배하게 됩니다. 그렇기 때문에 알파의 입장에서는 거리가 $m$을 초과하는 지점으로 룬석을 이동시키는 것이 최선의 전략이 됩니다.

 

이후 차례를 넘겨받은 베타에게도 이 전략은 동일하게 작용합니다. 역시 정해진 위치와의 거리가 $m$ 이하인 지점으로 룬석을 이동시키면, 차례를 넘겨받는 알파가 룬석을 정해진 위치로 옮길 수 있게 되어 베타가 패배하게 됩니다. 차례를 넘겨받은 베타의 입장에서도 거리가 $m$을 초과하는 지점으로 룬석을 이동시키는 것이 최선의 전략이 됩니다.

 

결국 상대방에게 승리를 안겨주고 싶지 않은 두 마법사들은 항상 거리가 $m$을 초과하는 지점으로만 룬석을 이동시키는 행동을 반복할 것이고, 게임은 영원히 끝나지 않게 됩니다.

코드

• C++17

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int limit, start_r, start_c, end_r, end_c;
        cin >> limit >> start_r >> start_c >> end_r >> end_c;

        int dist = abs(start_r - end_r) + abs(start_c - end_c);

        if (dist <= limit) {
            cout << "First 1\n";
        } else {
            cout << "Infinity\n";
        }
    }
}

• Python 3

N = int(input())

for _ in range(N):
    limit, start_r, start_c, end_r, end_c = map(int, input().split())
    dist = abs(start_r - end_r) + abs(start_c - end_c)

    if dist <= limit:
        print('First 1')
    else:
        print('Infinity')

• Node.js

const [, ...input] = require('fs')
  .readFileSync(0, 'utf-8')
  .trim()
  .split('\n');

let printer = '';

input.forEach((testcase) => {
  const [limit, startRow, startCol, endRow, endCol] = testcase.split(' ').map(Number);
  const dist = Math.abs(startRow - endRow) + Math.abs(startCol - endCol);
  
  if (dist <= limit) {
    printer += 'First 1\n';
  } else {
    printer += 'Infinity\n';
  }
});

console.log(printer);