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

• 유형 : DFS/BFS

코멘트

• 카카오 문제이지만 되게 삼성 같은(?) 문제다.
• 맨 처음에는 그냥 시뮬레이션처럼 풀었는데, 몇 개의 테스트 케이스가 통과하지 못해서 DFS/BFS로 접근했다.
• 문제에서 '맨해튼 거리'라고 어렵게 말했지만, 전형적인 BFS로 한 칸씩 이동할 때마다 거리를 +1 해주면 되는 문제이다.

설명

• 핵심 Idea : 모든 사람이 있는 좌표에서 BFS로 나와의 거리가 2 이하인 좌표가 하나라도 있는지 검사한다.
• 5개의 대기실마다 각각 아래 과정을 반복한다.
• 5*5의 모든 좌표마다,
  1. 이번 자리에 사람('P')이 앉아있는 경우에만 탐색을 진행한다. ('P'가 아니면 continue)
  2. BFS를 돌면서, 나와 다른 모든 사람의 거리를 구한다. (bfs()함수, 파티션('X')은 방문할 수 없음을 주의한다) 
  3. BFS를 다 돌고 나서, 거리가 2 이하인 '사람(P)'이 있나 체크한다. ( check()함수 )
• check()의 결과가 false이면 0을, true이면 1을 answer에 넣는다.

코드 (C++)

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

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int dist[6][6];

bool check(int tc, const vector<vector<string>> places) {
    // 거리가 2보다 작거나 같은 '사람'이 있나 체크한다.
    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            // -1이 아니면서, 거리가 2보다 작고, 걔가 사람이면 안된다
            if(dist[i][j] != -1 && dist[i][j] != 0) {
                if(dist[i][j] <= 2 && places[tc][i][j] == 'P') {
                    return false;
                }
            }
        }
    }

    // 끝까지 잘 왔으면 true 리턴
    return true;
}

void bfs(int a, int b, int tc, const vector<vector<string>> places) {
    // 시작점 큐에 넣기
    queue< pair<int, int> > q;
    dist[a][b] = 0;
    q.push(make_pair(a, b));

    // bfs 돌리기
    while(!q.empty()) {
        // 큐에서 하나 꺼내기
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 상하좌우 방문
        for(int k=0;k<4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            // 범위 유효하고
            if(!(nx>=0&& nx<5 && ny>=0 && ny<5)) continue;

            // 아직 방문 안했으면서 파티션이 아니면
            if(dist[nx][ny] == -1 && places[tc][nx][ny] != 'X') {
                // 맨해튼 거리 계산하고, 큐에 넣기
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}

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

    // 5개 대기실마다 반복
    for(int tc=0;tc<5;tc++) {
        bool flag = true;
        // 모든 좌표 검사
        for(int i=0;i<5;i++) {
            for(int j=0;j<5;j++) {
                char now = places[tc][i][j];

                // 이번 자리에 사람이 앉아있는 경우에만 나로부터 거리 검사
                if(now != 'P')  continue;

                // 이번 자리에 사람이 있는 경우, 나와 다른 모든 사람의 거리를 체크한다.
                memset(dist, -1, sizeof(dist));
                bfs(i, j, tc, places);

                // bfs 돌고 나서, 거리가 2보다 작거나 같은 '사람'이 있나 체크한다.
                // 그런 애가 있으면 false로 처리한다.
                if(!check(tc, places)) {
                    flag = false;
                    break;
                }
            }
            if(flag == false) break;
        }

        if(flag == false)   answer.push_back(0);
        else    answer.push_back(1);
    }

    return answer;
}

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

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