백준 17135번 캐슬 디펜스

김두현·2023년 1월 6일
백준
1

백준

목록 보기
55/133
post-thumbnail

🔒[문제 url]

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

🔑알고리즘

구현 순서는 다음과같다.
1. 궁수가 위치할 지점을 순열로 구현한다.
2. 3명의 궁수를 배치했다면, 각 궁수가 쏘게될 적 위치를 set 자료구조에 삽입한다.
3. 모두 활을 쐈다면, set을 순회하며 적을 없앤다.
4. 적을 아래로 한 칸씩 이동시킨다.
5. 적이 한 명도 없을때까지 2~4를 반복한다.
반복하는 동안,3에서의 set 크기의 누적 합 중 모든 순열에서의 최대값이 출력 답안이 된다.

🐾부분 코드

void copyMap()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            gameMap[i][j] = originMap[i][j];
}

<원본 map 복사>
디펜스 게임을 시작할 gameMap에 초기 상태인 originMap을 복사한다.

bool gameFinished()
{// 적이 하나도 없으면 true 반환
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(gameMap[i][j] == 1)
                return false;
    return true;
}

<맵에 적이 있는지 확인하는 함수>
맵 위에 적이 한 명이라도 있으면 false, 한 명도 없으면 true를 반환한다.

void enemyMove()
{// 적이 아래로 한 칸씩 이동

    // 제거된 적 0으로 표기
    for(set<pii>::iterator it = removed.begin(); it != removed.end(); it++)
        gameMap[it->first][it->second] = 0;
    removed.clear();

    // 가장 아랫 행부터 이동해야함에 주의한다.
    for(int i = n - 1; i >= 0; i--)
        for(int j = m - 1; j >= 0; j--)
        {
            if(gameMap[i][j] == 1)
            {
                // 적이 성이 있는 칸으로 이동하면 제외
                if(i != n - 1) gameMap[i + 1][j] = 1;
                gameMap[i][j] = 0;
            }
        }
}

<적 제거 후 아래로 이동하는 함수>
set 자료구조 변수인 removed에 속한 활에 맞은 적 지점을 순회하며 적을 제거한다.
이후 맨 아랫행의 적들부터 아래로 한 칸씩 이동시킨다.

void BFS(pii arch)
{// 활 쏘기

    queue<pii> q;
    q.push(arch);
    visited[arch.first][arch.second] = true;

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 3; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < n && 0 <= ny && ny < m)
            {// Check range
                if(!visited[nx][ny])
                {
                    if(gameMap[nx][ny] == 1
                    && (abs(arch.first - nx) + abs(arch.second - ny) <= d))
                    {// 거리가 d 이하인 적을 쐈다면
                        removed.insert({nx,ny}); // set에 적 위치 삽입
                        return; // 후 종료
                    }

                    // 쏘지 못했다면 이어서 탐색
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }

            }
        }
    }
    return;
}

<BFS로 활 쏘기>
3명의 궁수가 동시에 활을 쏜다.
이때 활에 맞은 적의 정보가 중복이 되지 않도록 set 자료구조인 removed에 저장한다.

int castleDefence()
{
    int score = 0; // 제거한 적의 수

    while(!gameFinished())
    {// 적이 없을때까지 반복

        // 모든 궁수가 활을 쏘고나면
        for (int i = 0; i < archer.size(); i++)
        {
            memset(visited, false, sizeof(visited));
            BFS(archer[i]);
        }
        // 제거한 적의 수만큼 답에 추가
        score += removed.size();
        // 적이 이동한다
        enemyMove();
    }
    return score;
}

<디펜스 진행 함수>
gameFinished() 함수를 통해 맵에 적이 없을때까지 활 쏘기와 이동을 반복한다. 이때 removed의 누적합이 현재 순열에서 쏘게 되는 적의 수이다.

void permutation(int cnt, int limit, int start)
{// 좌표계 순열 설정
    if(cnt == limit)
    {
        copyMap();
        ans = max(ans, castleDefence());
        return;
    }

    bool init = false;
    for(int j = 0; j < m; j++)
    {
        if(!init)
        {// 중복 순열 방지
            j = start;
            init = true;
        }

        if(!archerPos[n][j])
        {
            archer.push_back({n,j});
            archerPos[n][j] = true;
            permutation(cnt + 1, limit, j);
            //BackTracking
            archer.pop_back();
            archerPos[n][j] = false;
        }
    }
}

<궁수 위치 순열 설정 함수>
궁수가 위치할 지점을 중복되지 않게끔 BruteForcing + BackTracking으로 지정한다.
세 개의 지점이 모두 정해지면, 디펜스를 진행한다.

🪄전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <set>
using namespace std;

typedef pair<int,int> pii;
int n,m,d;
int gameMap[17][16], originMap[17][16];
bool archerPos[17][16];
bool visited[17][16];
vector<pii> archer;
set<pii> removed;
// D가 같으면 가장 왼쪽에 있는 적부터 공격 -> (좌 상 우) 순으로 BFS 진행
int dir[3][2] = {{0,-1},{-1,0},{0,1}};

int ans = 0;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> d;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> originMap[i][j];
}

void copyMap()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            gameMap[i][j] = originMap[i][j];
}

bool gameFinished()
{// 적이 하나도 없으면 true 반환
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(gameMap[i][j] == 1)
                return false;
    return true;
}

void enemyMove()
{// 적이 아래로 한 칸씩 이동

    // 제거된 적 0으로 표기
    for(set<pii>::iterator it = removed.begin(); it != removed.end(); it++)
        gameMap[it->first][it->second] = 0;
    removed.clear();

    // 가장 아랫 행부터 이동해야함에 주의한다.
    for(int i = n - 1; i >= 0; i--)
        for(int j = m - 1; j >= 0; j--)
        {
            if(gameMap[i][j] == 1)
            {
                // 적이 성이 있는 칸으로 이동하면 제외
                if(i != n - 1) gameMap[i + 1][j] = 1;
                gameMap[i][j] = 0;
            }
        }
}

void BFS(pii arch)
{// 활 쏘기

    queue<pii> q;
    q.push(arch);
    visited[arch.first][arch.second] = true;

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 3; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < n && 0 <= ny && ny < m)
            {// Check range
                if(!visited[nx][ny])
                {
                    if(gameMap[nx][ny] == 1
                    && (abs(arch.first - nx) + abs(arch.second - ny) <= d))
                    {// 거리가 d 이하인 적을 쐈다면
                        removed.insert({nx,ny}); // set에 적 위치 삽입
                        return; // 후 종료
                    }

                    // 쏘지 못했다면 이어서 탐색
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }

            }
        }
    }
    return;
}


int castleDefence()
{
    int score = 0; // 제거한 적의 수

    while(!gameFinished())
    {// 적이 없을때까지 반복

        // 모든 궁수가 활을 쏘고나면
        for (int i = 0; i < archer.size(); i++)
        {
            memset(visited, false, sizeof(visited));
            BFS(archer[i]);
        }
        // 제거한 적의 수만큼 답에 추가
        score += removed.size();
        // 적이 이동한다
        enemyMove();
    }
    return score;
}


void permutation(int cnt, int limit, int start)
{// 좌표계 순열 설정
    if(cnt == limit)
    {
        copyMap();
        ans = max(ans, castleDefence());
        return;
    }

    bool init = false;
    for(int j = 0; j < m; j++)
    {
        if(!init)
        {// 중복 순열 방지
            j = start;
            init = true;
        }

        if(!archerPos[n][j])
        {
            archer.push_back({n,j});
            archerPos[n][j] = true;
            permutation(cnt + 1, limit, j);
            //BackTracking
            archer.pop_back();
            archerPos[n][j] = false;
        }
    }
}

void SOLVE()
{
    permutation(0, 3, 0);
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

게임 느낌 나는 구현 문제는 오래 걸리지만 재밌어서 좋다.
마냥 즐기면 안 되고 구현 시간을 단축해야하긴하지만..ㅎㅎ
해결은 했으나 의문점이 남아있는 문제여서 질문도 남긴 문제다.
사실.. print 줄 단위로 찍어보고 비교해보면 되지만 조금 귀찮네요?

💕오류 지적 및 피드백은 언제든 환영입니다. 복제시 출처 남겨주세요!💕
💕좋아요와 댓글은 큰 힘이 됩니다.💕
profile
김두현
I AM WHO I AM
이전 포스트

백준 1038번 감소하는 수

다음 포스트

백준 5555번 반지

0개의 댓글