🌞문제

🌞접근법

조건1. 상대팀 진영을 먼저 파괴하면 이기는 게임이다.
조건2. 상대팀 진영에 최대한 빨리 도착하는 것이 유리하다.
조건3. 검은색 벽은 막혀있고, 흰색 부분은 갈 수 있다.
조건4. 캐릭터는 동서남북 방향으로 한칸씩 이동가능하다.
조건5. 상대팀 진영에 도착하지 못 할 수도 있다. 이 경우 -1을 리턴해라
조건6. maps 는 n x m 크기의 2차원 배열, n과 m은 1~100의 자연수
조건7. n과 m은 서로 같을 수 있지만, 두개가 1인 경우은 주어지지 않는다.
조건8. maps는 0과 1로만 이루어져 있다. 0은 벽이 있는 곳, 1은 벽이 없는 곳
조건9. 플레이어는 (1,1)에서 시작한다. 상대 진영은 (n,m)에 있다.

결과값 : 이 플레이어가 상대팀 진영에 도착하기 위한 칸 수의 최솟값을 구하라. 못가면 -1

이 문제의 경우 최소 경로를 탐색하는 문제이다.

이 문제는 현재 위치에서 동서남북을 먼저 이동을 한다.
그리고 해당 위치를 visit로 표시를 하고, 그 이후에 확인을 할 때 visit 된 상태라면 이에 관한 연산은 무시한다.
그렇게 하는 이유는 앞서 더 짧은 방법을 통해서 방문을 한 경우에 맞춰줄 것이기 때문이다.

그래서 어떻게 앞서 더 짧은 방법으로 방문을 하도록 해줄 것인가?
그 방법은 bfs를 이용하면 된다.

bfs는 너비 우선 탐색으로 그래프가 있을 때, 현재 내가 방문한 곳을 visit에 표시를 하고,
현재 위치에서 바로 이동 할 수 있는 인접한 공간을 큐에 추가한다.

위와 같이 할 때, 그리드 상에 표시되어있는 모든 공간에 최적의 이동값을 구 할 수 있을 것이다.
또한 이 방법은 visit 요소를 계속 확인하기 때문에 무한루프에 빠지는 일도 피할 수 있다.

bfs에 구현을 위해서는
1. x,y를 표현하는 큐의 요소를 만든다.
2. x,y를 방문했는지를 나타내는 visit 배열을 만든다.
3. x,y의 값이 n,m 일 때, count 값을 return 한다.

🌞답

#include<vector>
#include<iostream>
#include <queue>
using namespace std;


int visit[101][101];
int dx[4] = {0 , 0 , -1 , 1};
int dy[4] = {-1, 1 , 0 , 0};
int cnt = 0;

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    queue<pair<int,int>> q;
    int n=maps[0].size()-1;
    int m=maps.size()-1;
    visit[0][0] = 1;
    q.push(make_pair(0,0));
    
    while(!q.empty())
    {
        pair<int,int> pos = q.front();
        q.pop();
        
        int x = pos.second;
        int y = pos.first;
        
        for(int i=0;i<4;i++)
        {
            int _x = x+dx[i];
            int _y = y+dy[i];
                
            if(_x >= 0 && _x <= n && _y >=0 && _y <=m)
            {
                if(visit[_y][_x] == 0 && maps[_y][_x] > 0)
                {
                    q.push(make_pair(_y,_x));
                    visit[_y][_x] = 1;
                    maps[_y][_x] = maps[y][x] + 1;                   
                }
            }
        }
    }
    
    
    answer = maps[m][n];
    if(visit[m][n] == 0) answer= -1;
    
    return answer;
    
}