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

 

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

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

#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <iostream>

using namespace std;

struct Info {
    int x, y, dist;
};

// 맨해튼 거리(가로, 세로의 합) vs 유클리드 거리(최단 거리)
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    bool visited[5][5];
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };

    for (int i = 0; i < 5; i++) {
        memset(visited, 0, sizeof(visited)); // memory.h
        bool flag = false; // 거리두기 불가능 여부
        for (int j = 0; j < 5; j++) {
            if (flag) break;
            for (int k = 0; k < 5; k++) {
                if (flag) break;
                if (visited[j][k]) continue;
                if (places[i][j][k] == 'P') {
                    queue<Info> q;
                    q.push({ k,j,0 });
                    visited[j][k] = true;
                    
                    while (!q.empty()) {
                        if (flag) break;

                        int x = q.front().x;
                        int y = q.front().y;
                        int dist = q.front().dist;
                        q.pop();
                        
                        for (int l = 0; l < 4; l++) { // 인덱스 i 사용X
                            int newX = x + dx[l];
                            int newY = y + dy[l];
                            int newDist = dist + 1;

                            if ((newX < 0) || (newY < 0) || (newX >= 5) || (newY >= 5)) continue;
                            if (newDist > 2) continue; // 조건 위치(for 문 안O / 바깥X)
                            if (visited[newY][newX]) continue;
                            visited[newY][newX] = true;
                            if (places[i][newY][newX] == 'X') continue;
                            if (places[i][newY][newX] == 'P') {
                                answer.push_back(0);
                                flag = true;
                                break;
                            }
                            q.push({ newX, newY, dist + 1 });
                        }
                    }
                }
            }
        }
        if (!flag) answer.push_back(1);
    }

    return answer;
}