[프로그래머스 2021 카카오 채용연계형 인턴십] 거리두기 확인하기

문제

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

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

 

풀이

1. 5개의 대기실마다 검사를 해야하므로 하나의 대기실에 대해 검사하는 함수를 만들어 각 대기실마다 거리두기를 만족하는지 여부를 체크할 수 있습니다.

 

2. P의 주변을 확인할 때, 거리가 2이하이므로 총 12가지 인접위치를 하나 하나 검사해도 되고, bfs 혹은 dfs로 구현해도 됩니다. (아래의 코드에서는 bfs를 사용하였습니다.)

 

코드

#include <bits/stdc++.h>
using namespace std;

const int dir[4][2] = {{-1,0}, {1,0}, {0, -1}, {0, 1}};

bool check(string g[]){
    bool ret = 1, vis[5][5];
    auto bfs = [&](int r, int c) -> bool{
        memset(vis, 0, sizeof(vis));
        queue<tuple<int,int,int>> q;
        int cr, cc, nr, nc, d;
        q.push({r, c, 0});
        vis[r][c] = 1;
        while(!q.empty()){
            tie(cr, cc, d) = q.front(); q.pop();
            if (d <= 2 && !(cr == r && cc == c) && g[cr][cc] == 'P') return 0;
            for (int i = 0 ; i < 4; i++){
                nr = cr + dir[i][0], nc = cc + dir[i][1];
                if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5 || g[nr][nc] == 'X') continue;
                if (d <= 1) {
                    q.push({nr,nc,d+1});
                    vis[nr][nc] = 1;
                }
            }
        }
        return 1;
    };
    for (int i = 0; i < 5; i++)
        for (int j = 0 ; j < 5; j++)
            if (g[i][j] == 'P')
                ret &= bfs(i, j);
            return ret;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for (auto g : places){
        string grid[5];
        for (int i = 0 ; i < 5; i++) grid[i] = g[i];
        answer.push_back(check(grid));
    }
    return answer;
}