[프로그래머스] 거리두기 확인하기 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

1. 주의할 점

- BFS를 통해 해결하며, 무엇을 기준으로 수행 할 것인지 정한다

- TC마다 초기화를 수행한다

 

2. 구현

- Check[][] 배열을 통해 사람의 기준으로 1칸씩 이동했을 때, 도달 할 수 있는 자리를 저장한다

- TC마다 Avail, Queue, Idx, Check[][]를 초기화한다

- Places의 값이 사람이라면 Queue에 담고, 해당 자리를 몇 번째 사람인지 표시한다

- 맨해튼 거리가 2 → A사람이 1칸 움직였을 때 가능한 자리와  B사람이 1칸 움직였을 때 가능한 자리가 같다면 2다 → Queue안의 원소만큼만 사람을 퍼트렸을 때 안겹치면 1, 겹치면 0을 저장

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct info{
    int y,x;
};
int check[5][5];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int k=0;k<5;k++){
        queue<info> q;
        int avail=1;
        int idx=1;
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                check[i][j]=0;
                char c = places[k][i][j];
                if(c=='P'){
                    q.push({i,j});
                    places[k][i][j]='O';
                    check[i][j]=idx++;
                }
            }
        }
        //bfs
        while(!q.empty()){
            int cy = q.front().y;
            int cx = q.front().x;
            int cv = check[cy][cx];
            q.pop();
            for(int i=0;i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(nx>=0 && ny>=0 && nx<5 && ny<5){
                    if(places[k][ny][nx]=='X') continue;        //벽
                    if(check[ny][nx]==cv){      //시작점
                            
                    }
                    else if(check[ny][nx]==0){  //도달하지 않은 점
                        check[ny][nx]=cv;
                    }
                    else {      //다른 사람
                        avail=0;
                        break;
                    }
                }
            }
            if(avail!=1) break;    
        }
        answer.push_back(avail);
    }
    return answer;
}