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

문제

맨해튼 거리는 |r1 - r2| + |c1 - c2| 이다.

제한사항

5*5의 5개 대기실을 입력받아 조건을 충족했는지 확인하는 문제임을 파악할 수 있다.
각 대기실을 순회하며 거리두기를 지키는지 아닌지 파악하면 된다.

입출력

맨해튼 거리가 2라면, 전체 두 칸 움직여서 도착할 수 있는 거리이다.
특정 사람에서 출발하여 다른 사람까지 이동하는 데 2칸 이하면 거리두기를 지키지 않는 것이다.

5*5 거리이기 때문에 최대 25명의 사람이 앉을 수 있지만, 사실 한 명만 지키지 않으면 다른 사람들은 체크할 필요가 없기에,
이 문제는 각 사람들의 위치만큼의 BFS를 통해 감염 여부를 판정하는 문제임을 알 수 있다.

시행착오

• 처음에는 모든 사람을 동시에 BFS시키면서 지나간 길을 visited 처리하려 했으나,, 뻘짓이란 걸 깨닫고 5*5이므로 각 사람마다 BFS를 시도하였다.

소스 코드

#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <iostream>

using namespace std;

bool visited[5][5];
vector<int> answer;
vector<pair<int, int> > v;
bool flag;
char map[5][5];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void BFS(int sx, int sy){
    queue<pair<int, pair<int, int>>> q;
    q.push(make_pair(0, make_pair(sx, sy)));
    visited[sx][sy] = true;
    
    while(!q.empty()){
        int move = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();
        
        if(move >= 3) continue; // 전염 시도 실패
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
            if(visited[nx][ny]) continue;
            if(map[nx][ny] == 'X') continue;
            if(map[nx][ny] == 'P' && !visited[nx][ny] && move <= 1){ // 조건 충족(전염 성공)
                flag = true;
                return;
            }
            q.push(make_pair(move + 1, make_pair(nx, ny)));
            visited[nx][ny] = true;
        }
    }
}

vector<int> solution(vector<vector<string>> places) {    
    for(int a=0; a<5; a++){
        flag = false;
        v.clear();
        vector<string> strs = places[a];
        
        for(int i=0; i<5; i++){
            string str = strs[i];
            for(int j=0; j<5; j++){
                map[i][j] = str[j];
                if(str[j] == 'P'){ // 각 사람의 위치 저장
                    v.push_back(make_pair(i, j));
                }
            }
        } // 대기실 상황 저장
        
        for(int i=0; i<v.size(); i++){
            memset(visited, false, sizeof(visited));
            BFS(v[i].first, v[i].second); // 각 사람별로 BFS
            if(flag) break; // 한 명이라도 지키지 않았음 -> 이탈
        }
        if(flag) answer.push_back(0);
        else answer.push_back(1);
    }
    return answer;
}

교훈

• BFS인 걸 알았으면 기계처럼 빠르고 정확하게 코드를 작성할 수 있어야 한다.
• 코드를 빨리 칠 생각하지 말고 문제를 정확하게 이해하고 시작하자. 문제 이해를 잘못하면 큰 손해가 된다.