문제 푼 날짜 : 2021-07-21

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81302

접근 및 풀이

문제를 접했을 때, BFS 또는 DFS로 풀 수 있겠다 생각했다.
이 풀이는 BFS를 이용하여 구현했다.

1. 모든 대기실을 순회한다.
2. 각 대기실마다 응시자의 위치(P)를 저장한다.
3. 각 저장된 위치에서부터 BFS를 수행한다.
   3-1. 수행하면서 맨해튼 거리가 2이하인 경우가 있다면 즉시 return false
   3-2. 정상적으로 모두 끝나면 return true

코드

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

using namespace std;

struct src {
    int y, x, cnt;
};

vector<string> Room;
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }};

bool bfs(src s) {
    bool visited[5][5] = { false };
    queue<src> q;
    q.push(s);
    visited[s.y][s.x] = true;
    
    while (!q.empty()) {
        int nowY = q.front().y;
        int nowX = q.front().x;
        int nowCnt = q.front().cnt;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nextY = nowY + dir[i][0];
            int nextX = nowX + dir[i][1];
            
            if (nextY < 0 || nextY > 4 || nextX < 0 || nextX > 4) {
                continue;
            }
            if (Room[nextY][nextX] == 'X' || visited[nextY][nextX]) {
                continue;
            }
            if (Room[nextY][nextX] == 'P') {
                if (nowCnt + 1 <= 2) { 
                    return false;
                }
                visited[nextY][nextX] = true;
                continue;
            }
            q.push({ nextY, nextX, nowCnt + 1 });
            visited[nextY][nextX] = true;
        }
    }
    return true;    
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for (auto room : places) {
        Room = room;
        vector<pair<int, int>> position;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (room[i][j] == 'P') {
                    position.push_back(make_pair(i, j));
                }
            }
        }
        bool check = true;
        for (int i = 0; i < position.size(); i++) {
            if (bfs({ position[i].first, position[i].second, 0 }) == false) {
                check = false;
                answer.push_back(0);
                break;
            }
        }
        if (check == true) {
            answer.push_back(1);
        }
    }
    return answer;
}

결과

피드백

이 풀이보다 더 깔끔하고 짧은 코드가 많이 있었다.
그래도 문제를 보고 BFS를 떠올렸다는 거에 만족을...하지만 좀 더 문제를 풀어봐서 깔끔하게 코드를 짜는 연습도 필요할 것 같다.