[CodinGame] SHADOWS OF THE KNIGHT(이진 탐색으로 폭탄 찾기)

문제 간략 설명: 배트맨이 되어 건물에 설치된 폭탄의 위치를 찾는 것입니다.

[사진]

[Rules_규칙]

목표: 건물 어딘가 인질이 있는 방에 폭탄이 설치되어 있습니다. 배트맨의 임무는 창문을 넘나들면
서 폭탄이 설치된 방을 찾아 폭탄을 제거하고 인질을 구출하는 것입니다. 배트맨은 창문 이곳
저곳을 자유롭게 점프하며 다닐 수 있습니다. 하지만 폭탄이 터지기 전에 움직일 수 있는 횟
수는 제한되어 있으니 서둘러야 합니다.

 

규칙: 

1. 초기 입력으로 빌딩의 가로 세로 크기 W, H와 남은 점프 가능 횟수 N, 시작 위치 X0, Y0를 입력받는다.
2. 무한 루프를 돌며 매턴마다 폭탄이 있는 방향을 입력받는다.
3. 입력된 방향으로부터 폭탄이 있는 방향을 추정하고, 다음으로 이동할 윈도우의 위치를 출력한다.
4. 이동 가능한 방향은 U, UR, R, DR, D, DL, L, UL 중 하나이다.

[풀이 영상]

 

[문제]

 

https://www.codingame.com/training/medium/shadows-of-the-knight-episode-1

Practice Binary search and Intervals with the exercise "Shadows of the Knight - Episode 1"

 

[난이도]

[학습 개념]

[풀이]

• if문과 else if문을 이용해, bombDir 문자열에서 'U' 또는 'D' 문자가 발견되면, 배트맨의 이동을 위해 yStart와 yEnd 추측 범위를 좁힌다.
  • 'U' 문자가 포함되어 있다면, 현재 위치보다 위쪽에 폭탄이 있다는 뜻이므로, 추측 범위의 최하단인 yStart를 배트맨의 현재 위치 - 1로 변경한다.
  • 'D' 문자가 포함되어 있다면, 현재 위치보다 아래쪽에 폭탄이 있다는 뜻이므로, 추측 범위의 최상단인 yEnd를 배트맨의 현재 위치 + 1로 변경한다.
  • 두 문자가 모두 없다면, yStart와 yEnd는 현재 배트맨의 위치와 같다.
• if문과 else if문을 이용해, bombDir 문자열에서 'R' 또는 'L' 문자가 발견되면, 배트맨의 이동을 위해 xStart와 xEnd 추측 범위를 좁힌다.
  • 'R' 문자가 포함되어 있다면, 현재 위치보다 오른쪽에 폭탄이 있다는 뜻이므로, 추측 범위의 최좌단인 xStart를 배트맨의 현재 위치 + 1로 변경한다.
  • 'L' 문자가 포함되어 있다면, 현재 위치보다 왼쪽에 폭탄이 있다는 뜻이므로, 추측 범위의 최우단인 xEnd를 배트맨의 현재 위치 - 1로 변경한다.
  • 두 문자가 모두 없다면, xStart와 xEnd는 현재 배트맨의 위치와 같다.
• X0와 Y0를 새로운 추측 범위의 중간 값으로 업데이트한다.
  • 이를 위해, xStart와 xEnd를 더한 후 2로 나눈 값으로 X0를 업데이트한다.
  • 마찬가지로, yStart와 yEnd를 더한 후 2로 나눈 값으로 Y0를 업데이트한다.
• Console.WriteLine()을 이용해, 배트맨이 다음에 뛰어야 할 창문의 위치인 X0와 Y0를 출력한다.

 

 

[소스 코드]

 

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

class Player
{
    static void Main(string[] args)
    {
        string[] inputs;
        inputs = Console.ReadLine().Split(' ');
        int W = int.Parse(inputs[0]); // width of the building.
        int H = int.Parse(inputs[1]); // height of the building.

        int xStart = 0, xEnd = W - 1, yStart = H - 1, yEnd = 0; //이진 탐색으로 폭탄의 위치를 찾기 위해 추측 범위를 좁혀나가야함 이때 필요한 범위 값

        int N = int.Parse(Console.ReadLine()); // 최대 이동 수
        inputs = Console.ReadLine().Split(' ');

        int X0 = int.Parse(inputs[0]); //배트맨의 현재 위치
        int Y0 = int.Parse(inputs[1]);

        // game loop
        while (true)
        {
            string bombDir = Console.ReadLine(); // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)

            if (bombDir.Any(c => c == 'U'))
            {
                yStart = Y0 - 1; // 0으로 갈 수록 위쪽이라서 yStart 값에 배트맨의 Y위치 -1을 해줬다.
            }
            else if (bombDir.Any(c => c == 'D'))
            {
                yEnd = Y0 + 1;
            }
            else
            {
                yStart = yEnd = Y0;
            }

            if (bombDir.Any(c => c == 'R'))
            {
                xStart = X0 + 1; // Y 좌표와는 반대로 0으로부터 멀어질 수록 오른쪽 이라서 xStart 값에 배트맨의 Y위치 -1을 해줬다.
            }
            else if (bombDir.Any(c => c == 'L'))
            {
                xEnd = X0 - 1;
            }
            else
            {
                xStart = xEnd = X0;
            }

            //배트맨의 위치를 이진 탐색을 위해 추측 범위의 중간으로 옮겨야 함
            X0 = (xStart + xEnd) / 2;
            Y0 = (yStart + yEnd) / 2;
            // the location of the next window Batman should jump to.
            Console.WriteLine(X0 + " " + Y0);
        }
    }
}

 

[새롭게 알게된 점]

1. 이진 탐색(binary search)을 이번 기회에 공부해 보았습니다. 남은 탐색 구간을 반(2)으로 줄이기 때문에 숫자 2를 의미하는 바이너리(binary)라고 부른다는 걸 새롭게 알았습니다. 이제 이진 탐색은 탐색 구간을 반으로 나눠서 탐색한다는 걸 머릿속에 콕 박혔습니다. 물론 사전 작업으로 탐색할 데이터가 정렬되어 있어야 된다는 것도 알게 되었습니다.

2. 좌표의 기준이 죄상단이기 때문에 위아래가 혼동될 수 있었는데 변수명을 minY, maxY 같은 걸로 했다가 더 헷갈려서 무슨 변수명이 더 직관적일까 고민하다 지금의 변수명으로 하니 헷갈리는게 줄었습니다. 변수명을 잘 지으면 오류가 덜 한다는 걸 다시 한번 깨달았습니다.