몇번 풀어봄

• 21년 10월 7일 목요일

풀이전략만 잘세우고, 겁만 안먹으면 100프로 풀 수 있었다.

풀이전략

• 대각선 거리는 1.414가 아니라 2차이가 난다. 그냥 한칸 한칸씩 진행하는 방식으로 이전의 좌표를 이용하는 것이다.

주의할점

• 예외처리를 잘해야 한다.
  
  -> 5라고 해서 segment error 발생했다.

• 놓친 점으로는 (0,0)에서 (1,0)으로 이동한수 (0,0)을 다시 탐색할 수 있으므로 그에 대한 불변수를 사용해야 한다.
  이 부분을 놓쳤다.
  

소스코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

//왜 bfs로 접근하냐면 P인 지점에서부터 상하좌우로 2번씩 움직이면서 P의 여부를 확인하는 방식이다.
//게임 맵 최단거리 문제와 비슷하다.
//이전 거리의 + 1씩 추가를 하므로 bfs이다.

bool bfs(vector<string>place)
{  
    vector<vector<char>>v(place.size(), vector<char>(place[0].size()));
    
    vector<vector<bool>>check(place.size(), vector<bool>(place[0].size(), false));
    
    for(int i = 0; i < place.size(); i++)
    {
        for(int j = 0; j < place.size(); j++)
        {
            v[i][j] = place[i][j];
        }
    }
    
    
    //상하좌우 
    int right[4] = {0,0,-1,1};
    int up[4] = {-1,1,0,0};
    
    for(int i = 0; i < place.size(); i++)
    {
        for(int j = 0; j< place.size(); j++)
        {
            if(v[i][j] == 'P')
            {
                //first : y , second : x
                queue<pair<pair<int,int>, int>>q; 
                q.push({{i,j}, 0});
                
                while(!q.empty())
                {
                    int curY = q.front().first.first;
                    int curX = q.front().first.second;                  
                    int num = q.front().second;
                    q.pop();
                    
                    if(check[curY][curX])
                        continue;
                    check[curY][curX] = true;
                    
                    
                    if(num == 2)
                        continue;
                                        
                    for(int k = 0; k < 4; k++)
                    {
                        int nextX = curX + right[k];
                        int nextY = curY + up[k];
                                    
                        //이 부분 예외처리 방심했다. >5라고 함.
                        if (nextX < 0 || nextX > 4
							|| nextY < 0 || nextY > 4)
							continue;
                        if(check[nextY][nextX])
                            continue;
                        
                        if(v[nextY][nextX] == 'O')
                        {
                            q.push({{nextY, nextX}, num + 1});
                        }
                        else if(v[nextY][nextX] == 'P')
                        {
                            return false;
                        }
                    }    
                } 
            }
            
        }
    }
        
    return true;
}


vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int i = 0; i <places.size(); i++)
    {
        if(bfs(places[i]))
            answer.push_back(1);
        else 
            answer.push_back(0);
    }
    
    //대기실마다 확인해야 한다. 
    
    
           
    
    
    
    
    
    return answer;
}