[백준 25585번] [Java, Kotlin] 86 ─에이티식스─ 1

https://www.acmicpc.net/problem/25585

25585번: 86 ─에이티식스─ 1

 

난이도 : 골드 5
태그 : 백트래킹, 브루트포스

 

 

설명

대각선으로만 이동할 수 있는 장기말로, 다른 적들을 다 잡을 수 있는지,

잡을 수 있다면 얼마만큼의 시간이 소요되는지 구하는 문제입니다.

 

처음엔 n이 꽤 작길래, 대각선 방향으로 이동하는 모든 경우의 수를 다 확인하였으나,

당연하게도 시간초과. n이 최대 100이여도 n이 1 만큼 증가할때마다 말도안되게 경우의 수가 늘어났던게 이유였던듯 하네요.

 

좀 다르게 접근하여,

한 칸씩 탐색하는 것이 아닌, 적의 장기말로 직접 접근하여

장기말을 잡는 모든 순서를 탐색해보기로 했습니다.

 

 

적의 장기말을 모두 잡을 수는 없는 경우?

해당 문제의 장기말의 이동 방식은 체스의 비숍과 동일합니다. 대각선으로만 이동할 수 있죠.

 

 

대각선으로만 이동 가능하다는 것은, 비숍은 게임이 진행되는 내내 같은 색깔의 칸에서만 싸울 수 있다는 말과 같습니다.

위 그림의 연두색은 비숍, 빨간색은 검은색 칸에 위치한 적, 파랑색은 흰 색 칸에 위치한 적 입니다.

 

검은색 칸에서 시작한 비숍은 오직 검은색 칸에 있는 적들만 잡을 수 있습니다.

파란색의 적, 즉 흰 칸에 위치한 적은 잡을 수 없지요.

 

 

위 그림을 기준으로, 비숍이 검은색 칸에 있다면 (2,4) 행과 열 모두 짝수입니다.

검은색칸(1,3)에 위치한 적의 좌표는 행과 열 모두 홀수입니다.

즉, 검은색 칸은 행과 열이 모두 짝수이거나 홀수입니다.

 

반면의 흰색칸은 행이 홀수일 경우 열이 짝수, 행이 짝수일 경우 열이 홀수입니다.

 

행, 열을 2로 나눴을때 나머지가 서로 같냐, 서로 다르냐로 칸의 색깔을 구할 수 있습니다.

장기말과 적의 장기말의 칸이 모두 같다면 적을 모두 잡을 수 있고,

하나라도 다른 색의 칸에 장기말이 있다면 적을 모두 잡을 수 없는 경우입니다.

 

 

 

비숍의 이동 거리(시간)?

대각선으로 1칸 만큼 이동하는데 1의 시간이 든다 하였으므로,

해당 문제에서 이동하는데 걸린 시간은 두 말의 거리와 같다고 봐도 무방합니다.

 

연두색에서 목표인 빨간색까지 총 7칸을 움직였습니다.

대각선으로만 이동할 수 있기 때문에, 지그재그로 이동해야 하는 구간이 생깁니다만,

총 이동한 칸 시작점과 도착점의 가로 길이, 세로 길이 중 큰 값과 같습니다.

(3, 1)에서 (6, 8)로 가는데 세로로 3칸, 가로로 7칸 움직였고,

총 움직인 칸은 7칸으로, 가로/세로로 움직인 길이 중 큰 값과 같죠.

 

즉, 시작점의 위치를 (x1, x2), 도착점의 위치를 (x2,y2) 라고 한다면,

두 칸의 거리(=이동하는데 걸린 시간)는 max(abs(x1-x2), abs(y1-y2)) 와 같습니다.

 

자, 모든 적을 잡을 수 있는지 판단하는 법과,

이동거리를 구하는 법을 알아봤으니,

이제 백트래킹으로 적을 잡는 모든 순서를 탐색하여 그 중 가장 적은 시간(=거리)이 걸린 경우를 찾으면 됩니다.

적의 수는 최대 10개이니, 충분히 시간 안에 통과가 가능할 것 같네요.

 

 

 

소스코드

Kotlin

import kotlin.math.abs

data class Point(val x: Int, val y: Int)

lateinit var enemyVisited: BooleanArray
lateinit var map: Array<IntArray>
val enemies = ArrayList<Point>()
var n = 0
var minTime = Int.MAX_VALUE

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()

    var startX = 0
    var startY = 0

    map = Array(n) { IntArray(n) }

    for (i in 0 until n) {
        val input = readLine().split(" ").map { it.toInt() }
        for (j in 0 until n) {
            map[i][j] = input[j]

            // 시작 위치
            if (map[i][j] == 2) {
                startX = i
                startY = j
            } else if (map[i][j] == 1) {
                // 적의 위치
                enemies.add(Point(i, j))
            }
        }
    }

    // 대각선으로만 이동 가능함
    // 체스의 비숍 이동 방식 -> 다른 색깔의 칸에 적이 있으면 불가능
    if (startX % 2 == startY % 2) {
        enemies.forEach { enemy ->
            if (enemy.x % 2 != enemy.y % 2) {
                println("Shorei")
                return
            }
        }
    } else {
        enemies.forEach { enemy ->
            if (enemy.x % 2 == enemy.y % 2) {
                println("Shorei")
                return
            }
        }
    }

    enemyVisited = BooleanArray(enemies.size)

    backTracking(startX, startY, 0, 0)

    println("Undertaker")
    println(minTime)
}

fun backTracking(x: Int, y: Int, time: Int, depth: Int) {
    if (depth == enemies.size) {
        minTime = minOf(minTime, time)
        return
    }

    for (i in 0 until enemies.size) {
        if (enemyVisited[i]) continue

        val (nx, ny) = enemies[i]
        // 해당 적의 위치까지 이동하는데 걸리는 시간. 비숍의 이동 방식과 동일
        val spentTime = maxOf(abs(x - nx), abs(y - ny))

        enemyVisited[i] = true
        backTracking(nx, ny, time + spentTime, depth + 1)
        enemyVisited[i] = false
    }
}

 

 

 

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class _86_에이티식스_1_자바 {

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[][] map;
    static int n;
    static boolean[] enemyVisited;
    static ArrayList<Point> enemies = new ArrayList<>();
    static int minTime = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        int startX = 0, startY = 0;

        for (int i = 0; i < n; i++) {
            String[] split = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(split[j]);
                if (map[i][j] == 2) {
                    startX = i;
                    startY = j;
                } else if (map[i][j] == 1) {
                    enemies.add(new Point(i, j));
                }
            }
        }

        if (startX % 2 == startY % 2) {
            for (Point enemy : enemies) {
                if (enemy.x % 2 != enemy.y % 2) {
                    System.out.println("Shorei");
                    return;
                }
            }
        } else {
            for (Point enemy : enemies) {
                if (enemy.x % 2 == enemy.y % 2) {
                    System.out.println("Shorei");
                    return;
                }
            }
        }

        enemyVisited = new boolean[enemies.size()];
        backTracking(startX, startY, 0, 0);

        System.out.println("Undertaker");
        System.out.println(minTime);
    }

    private static void backTracking(int x, int y, int time, int depth) {
        if (depth == enemies.size()) {
            minTime = Math.min(minTime, time);
            return;
        }

        for (int i = 0; i < enemies.size(); i++) {
            if (enemyVisited[i]) continue;
            enemyVisited[i] = true;

            Point enemy = enemies.get(i);

            int spentTime = Math.max(Math.abs(x - enemy.x), Math.abs(y - enemy.y));
            backTracking(enemy.x, enemy.y, time + spentTime, depth + 1);
            enemyVisited[i] = false;
        }
    }
}

 

 

 

 

후기

골드5라 별 생각 없이 도전했다가, 생각보다 시간이 좀 걸렸던 문제였습니다.