프로그래머스 거리두기 확인하기 C++

문제설명

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

---

입출력 예

placesresult

[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

[1, 0, 1, 1, 1]

---

입출력 예 설명

입출력 예 #1

첫 번째 대기실

No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

• (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

• 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

• 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

---

제한시간 안내

• 정확성 테스트 : 10초

---

1. 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. 

 

 

 

#include <string>
#include <vector>
#include <cstring>
using namespace std;

bool flag; //참이면 거리두지 않은 것, 거짓이면 거리둔 것
bool visited[5][5]; //갔다왔는지 확인할 boolean형 배열
const int dy[]={-1,1,0,0};
const int dx[]={0,0,-1,1};

bool valid(int y, int x) 
{
    if(y>=0 && y<5 && x>=0 && x<5)return true;
    else return false;
}

void dfs(int y, int x, vector<string>& board, int depth) {
    //거리를 두지 않았거나, 맨해튼거리가 2초과인 경우
    if(flag || depth>2) return;

    // 맨해튼거리는 경우에 맞지만, 사람이 거리안에 있는경우
    if(depth>0 && board[y][x]=='P') {
        flag=true;
        return;
    }

    visited[y][x]=true;

    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(!valid(ny,nx) || visited[ny][nx] || board[ny][nx]=='X')
            continue;
        dfs(ny,nx,board,depth+1);
    }
}

bool solve(vector<string>& board) {
    //player의 위치좌표 
    vector<pair<int,int>> people;
    
    for(int i=0;i<board.size();i++)
        for(int j=0;j<board[i].size();j++)
            if(board[i][j]=='P') people.push_back({i,j});

    for(auto coo:people)//coordinate : 좌표
    {
        flag=false;
        memset(visited,false,sizeof(visited));//false로 초기화
        dfs(coo.first, coo.second,board,0);
        if(flag) return false;
    }

    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(auto a:places)
    {
        if(solve(a)) answer.push_back(1);
        else answer.push_back(0);
    }
    return answer;
}

 

=> DFS 와 BFS를 통해 depth를 맨해튼거리로 생각하여 풀면 되는 문제였습니다. 

=> 다른분들의 블로그를 참조하여 풀었습니다. 

=> flag가 참이 되는 순간, 거리두기가 지켜지지 않은 것입니다.

=> 기본적인 풀이는 아래의 그림을 참조해주시기 바랍니다.

 

기본풀이