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

 

 

 

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

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

 

 

 

 

이번 문제는 BFS 문제였습니다.

 

 

 

 

 

《문제 풀이》

 

1. places 배열의 각 행을 place 배열에 저장 (각 대기실을 탐색하기 위해)

2. place 배열을 탐색하면서 응시자를 만나면 거리두기 확인하기 ← BFS 시작

     (1) 현재 노드의 상/하/좌/우 노드가 이미 방문한 노드이거나 파티션이면 continue

     (2) 응시자 사이의 거리가 2 이하이면 false 반환 

3. 결과 값이 false이면 현재 대기실 탐색을 종료하고 answer 배열에 0 삽입

 

 

 

 

 

《C++ 코드》

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<string> place;

typedef struct {
    int x, y, d;
}info;

typedef struct {
    int x, y;
}box;

// 상 하 좌 우
box moveD[4] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

bool checkDistance(int x, int y) {
    bool visited[5][5] = { false, };
    queue<info> q;
    visited[x][y] = true;
    q.push({ x, y, 0 });
    
    while (!q.empty()) {
        int cx = q.front().x;
        int cy = q.front().y;
        int d = q.front().d;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int nx = cx + moveD[i].x;
            int ny = cy + moveD[i].y;
            
            if (nx < 0 || 5 <= nx || ny < 0 || 5 <= ny)
                continue;
            
            // 이미 방문한 노드이거나 파티션이면
            if (visited[nx][ny] || place[nx][ny] == 'X')
                continue;
            
            // 응시자이면 맨해튼 거리가 2 이하인지 확인
            if (place[nx][ny] == 'P') {
                if (d + 1 <= 2) {
                    return false;
                }
            }
            
            visited[nx][ny] = true;
            q.push({ nx, ny, d + 1 });
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for (auto p : places) {
        bool result = true;
        place = p;
        
        for (int i=0; i<5; i++) {
            for (int j=0; j<5; j++) {
                if (place[i][j] == 'P') { // 응시자이면 거리두기 확인하기
                    if (!checkDistance(i, j)) {
                        result = false;
                        break;
                    }
                }
            }
            
            if (!result) break; // 현재 대기실 탐색 종료
        }
        
        // 현재 대기실에 거리두기를 지키지 않는 응시자가 있다면 0 삽입
        if (!result) answer.push_back(0);
        else answer.push_back(1);
    }
    
    return answer;
}

 

 

 

 

프로그래머스 - 정답 화면