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

 

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

---

 

해결전략

 

너비우선탐새 BFS

 

 

별 위치 확

---

 

정답 코드

 

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

int dirY[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
int dirX[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };

vector<int> solution(vector<vector<string>> v) {
    vector<int> answer;

    for (int k = 0; k < v.size(); k++) 
    {
        queue<pair<int, int>> Q; // 'P'의 위치를 저장할 큐

        for (int y = 0; y < v[0].size(); y++) {
            for (int x = 0; x < 5; x++) {
                if (v[k][y][x] == 'P') Q.push({ y, x }); // 'P'를 찾아 넣음
            }
        }

        bool isRight = true; // 규칙에 맞는지 검사하는 플래그

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

            // 상하좌우
            for (int i = 0; i < 4; i++) {
                int ny = y + dirY[i];
                int nx = x + dirX[i];

                if (ny < 0 || v[k].size() <= ny || nx < 0 || 5 <= nx) continue;

                if (v[k][ny][nx] == 'P') { // 다음 위치가 'P'이면 규칙에 위배
                    isRight = false;
                    break;
                }
                else if (v[k][ny][nx] == 'O') { // 다음 위치가 빈 테이블('O')이면 또 다음 위치를 검사
                    int nny = ny + dirY[i]; // 다다음 y좌표
                    int nnx = nx + dirX[i]; // 다다음 x좌표

                    if (nny < 0 || v[k].size() <= nny || nnx < 0 || 5 <= nnx) continue;

                    if (v[k][nny][nnx] == 'P') { // 2칸 넘어에 응시자(다다음 위치가 'P'이면 규칙에 위배)
                        isRight = false;
                        break;
                    }
                }
            }
            // 대각선 4방향
            if (isRight)
            {
                for (int i = 4; i < 8; i++) {
                    int ny = y + dirY[i];
                    int nx = x + dirX[i];

                    if (ny < 0 || v[k].size() <= ny || nx < 0 || 5 <= nx) continue;

                    if (v[k][ny][nx] == 'P') { // 다음 위치가 'P'이면 'P'와의 경로에 'O'가 있는지 검사
                        if (v[k][y][nx] == 'O') {
                            isRight = false;
                            break;
                        }
                        if (v[k][ny][x] == 'O') {
                            isRight = false;
                            break;
                        }
                    }

                    if (isRight == false) break;
                }
            }
        }

        // 규칙에 맞으면 1, 아니면 0을 결과 벡터에 추가
        if (isRight) answer.push_back(1);
        else answer.push_back(0);
    }
    
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << " ";
    }
    
    return answer;
}

int main() {
    vector<vector<string>> testcase = {
        {"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"},
        {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"},
        {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"},
        {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"},
        {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"} };

    vector<vector<string>> testcase1 = {
        {"POOPO", "OOOOO", "OOOXP", "OPOPX", "OOOOO"} }; // 0

    solution(testcase);

    return 0;
}

 

 

 

---