백준 1584번 - 게임 (C++)

문제

해결 방법

Astar를 변형하여서 길찾기 알고리즘을 구현하였다.

 

아쉬웠던 점

길의 경로를 구하는 문제가 아니기 때문에 list를 이용하여 구현하기 보다는 우선순위 큐를 사용하여서 구현했으면 더 깔끔했을 것 같다.

 

코드

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
 
int Map[501][501] = {}; //해당 칸의 속성(안전 위험 죽음)을 0/1/2로 저장해두는 열
int MapList[501][501] = { 1, 0 }; //해당 칸을 탐색했는지 체크하는 배열. 탐색 했다면 1로 변경.(사실상 bool타입)
int MapOpenListHp[501][501] = {}; //해당 칸 까지 이동하는데 감소되는 HP의 최솟값을 저장
int X[4] = { 1, -1, 0, 0 }; //우 좌 상 하
int Y[4] = { 0, 0, 1, -1 };
 
struct AStar
{
    AStar(int a, int b) : x(a), y(b) {}
    int x;
    int y;
 
    bool operator== (const AStar a)const
    {
        return x == a.x && y == a.y;
    }
};
 
list<AStar> Openlist; //내가 이동할 수 있는 후보군을 저장하는 리스트
 
int Game()
{
    //출발지인 0,0을 탐색 후보군에 추가함.
    Openlist.emplace_back(AStar(0, 0));
 
    //도착지가 [죽음]구역이면 도착할 수 없음으로 예외처리 해줌
    if (Map[500][500] == 2)
        return -1;
 
    //반복하며 길찾기
    while (true)
    {
        //hp최소값 찾기
        int HpMin = 9999999, SaveX = 0, SaveY = 0;
        for (auto& i : Openlist)
        {
            if (MapOpenListHp[i.x][i.y] < HpMin)
            {
                HpMin = MapOpenListHp[i.x][i.y];
                SaveX = i.x;
                SaveY = i.y;
            }
        }
 
        //해당 구역을 탐색했으니 일단 후보군에서 제거.
        Openlist.remove(AStar(SaveX, SaveY)); 
 
        //주변 구역 후보군list에 추가
        for (int j = 0; j < 4; ++j)
        {
            int Xx = SaveX + X[j], Yy = SaveY + Y[j];
            if (Xx < 0 || Xx > 500 || Yy < 0 || Yy > 500) //범위밖이면 continue
                continue;
            else if (Xx == 500 && Yy == 500) //500 500이라면 리턴. 
                return MapOpenListHp[SaveX][SaveY] + Map[Xx][Yy]; //return (지금 칸 까지 필요한 Hp값 + 500,500의 위험도)
        
            if (MapList[Xx][Yy] == 0 && Map[Xx][Yy] != 2) //만약 탐사하지도 않았었고, 해당 구역의 타입이 죽음(2)가 아니라면
            {
                MapOpenListHp[Xx][Yy] = MapOpenListHp[SaveX][SaveY] + Map[Xx][Yy]; //해당 칸의 hp값을 (지금 칸 까지 필요한 Hp값 + 해당 칸의 위험도)로 입력하고,
                Openlist.emplace_back(AStar(Xx, Yy)); //후보군에 추가함
                MapList[Xx][Yy] = 1; //해당 칸을 탐색을 했다고 체크해줌.
            }
        }
 
        //후보군이 비어있다 = 길이 막혀서 진행이 불가능하기 때문에 불가능(-1)을 리턴함.
        if (Openlist.empty())
            return -1;
    }
}
 
void Input(int Num, int _a)
{
    for (int i = 0; i < Num; ++i)
    {
 
        int x1, y1, x2, y2;
        cin >> x2 >> y1 >> x1 >> y2;
 
        if (x1 > x2)
        {
            int c = x1;
            x1 = x2;
            x2 = c;
        }
        if (y1 > y2)
        {
            int c = y1;
            y1 = y2;
            y2 = c;
        }
 
        for (int j = x1; j <= x2; ++j)
        {
            for (int k = y1; k <= y2; ++k)
            {
                Map[j][k] = _a;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int a;
    cin >> a;
    Input(a, 1); //위험 구역 입력
    cin >> a;
    Input(a, 2); //죽음 구역 입력
 
    cout << Game();
}

진행 과정은 Astar를 변형하여 만들었으며, 0,0부터 시작하여서 주변 칸들을 모두 후보군에 넣고, 후보군중에서 해당 칸으로 진행하는데 필요한 Hp값이 가장 낮은 칸을 우선으로 탐색하여 다시 해당 칸의 주변 칸을 후보군에 넣음을 반복하였다.

설명은 주석으로 대체함.

 

잡설 : 1584번 코드 풀이는 내가 처음이다 ㅎ