[C++][프로그래머스] 2021 카카오 인턴십 문제, 거리두기 확인하기

[문제]

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

 

[문제조건]

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

 

[문제 해설]

응시자, 책상, 파티션 정보가 담긴 vector<string> 이 주어지고,

응시자들이 맨허튼 거리를 잘 유지하고 있는지 탐색하면 된다.

 

이 때, 맨허튼 거리는 두 좌표 (r1, c1), (r2, c2)가 주어졌을 때,

｜r1-r2｜+｜c1-c2｜로 판단 가능하다.

 

예를 들어, (0, 0), (2, 0)의 좌표라면 ｜0-2｜+｜0-0｜= 2 이므로

이 좌표사이에 파티션이 존재하지 않는데 P가 있으면 안된다. (아래 이미지 참조)

즉, 단순히 3x3 행열 범위만 파악하면 안되는 이유이다. 

얼핏 보면, 거리두기를 모두 만족하는 것 같지만,

(0, 0)과 (2, 0)의 P 는 맨허튼 거리가 2이고 빈 책상이 사이에 있으므로 거리두기를 지키지 않은 강의실이다.

 

 

[풀이 해설 및 코드]

; P의 좌표에서 맨허튼거리까지를 BFS로 탐색하면서 또 다른 P를 만나는지를 확인하는 방법으로 풀었다.

 

1) P의 모든 좌표를 pair vector에 넣어두고 vector 사이즈만큼 탐색을 진행한다.

vector<pair<int, int>> person_seats 변수.

 

2) 첫번째 person_seats 좌표부터 BFS로 상하좌우를 탐색한다. queue<pair<int, int>> q 변수와 direction[4][2] 변수로.

이 때, 재방문을 막기 위해 방문체크변수에 방문여부를 체크한다. 이 때, X,Y 범위를 넘지 않는지, 이미 방문했던 곳은 아닌지를 체크하면서 탐색한다.

 

3) 다음 좌표가 P라면 맨허튼 거리 2 안에 있는 좌표이면서 P가 또 존재한다는 말이므로 거리두기를 지키지 않았다는 말이다. false 값을 리턴해준다.

 

4) 다음 좌표가 O라면 빈자리이므로 해당 좌표를 다시 탐색해야 하므로 queue에 넣어주고, 방문체크해준다.

 

5) 한번 상하좌우로 BFS 탐색을 하게 되면 깊이가 1인 곳을 다 탐색하는 게 된다. 깊이는 맨허튼 거리와도 같다.

 

7) 다시한번 BFS 탐색을 진행하고, 깊이가 2인 곳 = 맨허튼 거리가 2인곳 까지 봐준다.

 

8) 다시 BFS 탐색을 진행할 때, 맨허튼거리가 2라면, 다음 탐색은 맨허튼거리 3인 좌표가 된다. 즉, 이미 2인거리까지 탐색했다는 의미이므로 해당 P의 좌표는 더이상 볼 필요가 없다. break문으로 다음 P의 좌표를 탐색하기 위해 빠져나온다.

if (abs(person_seats[i].first - curX) + abs(person_seats[i].second - curY) == 2) break; 가 바로 이 부분 !

 

9) 모든 P의 좌표를 다 탐색했는데 return false문을 만나지 않았다면, 모든 좌표가 거리두기를 만족했다는 의미이므로 true를 리턴해준다.

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

bool checkSeat(vector<string>, vector<pair<int, int>>);

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

	for (int i = 0; i < 5; i++) {//강의실 5개
		vector<pair<int, int>> person_seats;
		for (int row = 0; row < 5; row++) {//한 강의실 내의 한 행
			for (int col = 0; col < 5; col++) {//한 강의실 내의 한 열
				if (places[i][row][col] == 'P') {
					person_seats.push_back(make_pair(row, col));
				}
			}
		}
		checkSeat(places[i], person_seats) ? answer.push_back(1) : answer.push_back(0);
	}
	return answer;
}


bool checkSeat(vector<string> classroom, vector<pair<int, int>> person_seats) {//BFS
	int direction[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; //위, 오른쪽, 아래, 왼쪽

	for (int i = 0; i < person_seats.size(); i++) {
		int visited[5][5] = { 0, };
		queue<pair<int, int>> q;

		q.push(make_pair(person_seats[i].first, person_seats[i].second));
		visited[person_seats[i].first][person_seats[i].second] = 1;

		while (!q.empty()) {
			int curX = q.front().first;
			int curY = q.front().second;
			q.pop();

			if (abs(person_seats[i].first - curX) + abs(person_seats[i].second - curY) == 2) break;

			for (int i = 0; i < 4; i++) {
				int nextX = curX + direction[i][0];
				int nextY = curY + direction[i][1];
				if (nextX >= 0 && nextX < 5 && nextY >= 0 && nextY < 5 && visited[nextX][nextY] == 0) {
					if (classroom[nextX][nextY] == 'P') return false;
					else if (classroom[nextX][nextY] == 'O') {
						visited[nextX][nextY] = 1;
						q.push(make_pair(nextX, nextY));
					}
				}
			}
		}
	}
	return true;//거리두기를 지키지 못한 경우를 다 통과했다면, 거리두기를 잘 지킨 것.
}

 

참고로... 틀린 풀이 및 틀린 코드는... 걍 참고만...

 

첨엔 맨허튼 거리가 2x2 안인줄 알고,

브루트포스로 P의 좌표를 pair vector에 모두 저장한 후,

vector가 빌 때까지 탐색하는 데,

 

거리두기를 지키지 않았다는 조건으로

 

P의 상하좌우에 P가 있을 때와

P 상하좌우에 O가 있고 대각선에 P가 있을 때로 둬서 if문으로 단순무식하게 짰다.

 

결과는 3, 8, 9, 12번 테스트 케이스 실패.  

테스트 케이스를 찾아보고 맨허튼 거리의 참된 의미를 알게 되었다... 하하...

 

문제 조건 잘 읽자...

구현인줄 알고 단순무식하게 짰는데 안되면, BFS/DFS/DP 등 알고리즘 쪽으로 생각해보자.

문제에서 요구하는 바가 아닐 수도 있다!! 쫌만 더 집중해서 코딩하자...

 

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

bool checkSeat(vector<string>, vector<pair<int,int>>);

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

    for(int i = 0; i < 5; i++){//강의실 5개
        vector<pair<int,int>> person_seats;
        for(int row = 0; row < 5; row++){//한 강의실 내의 한 행
            for(int col = 0; col < 5; col++){//한 강의실 내의 한 열
                if(places[i][row][col]=='P'){
                    person_seats.push_back(make_pair(row,col));
                }
            }
        }
        checkSeat(places[i], person_seats) ? answer.push_back(1) : answer.push_back(0);
    }
    return answer;
}


bool checkSeat(vector<string> classroom, vector<pair<int,int>> person_seats){
    int direction[5][2] = {{0,1},{1,0},{-1,0},{1,1},{1,-1}}; //오른쪽, 아래, 왼쪽, 오른쪽 대각선, 왼쪽 대각선

    for(int i = 0; i < person_seats.size(); i++){
        int curX = person_seats[i].first;
        int curY = person_seats[i].second;
        for(int i = 0; i<3; i++){//오른쪽, 아래, 왼쪽 확인
            int nextX = curX + direction[i][0];
            int nextY = curY + direction[i][1];
            if(nextX < 0 || nextX >= 5 || nextY < 0 || nextY >= 5) continue;
            if(classroom[nextX][nextY] == 'P'){
                return false;
            }
            else if(classroom[nextX][nextY] == 'O'){
                for(int j = 3; j < 5; j++){//오른쪽 대각선, 왼쪽 대각선 확인
                    nextX = curX + direction[j][0];
                    nextY = curY + direction[j][1];
                    if(nextX < 0 || nextX >= 5 || nextY < 0 || nextY >= 5) continue;
                    if(classroom[nextX][nextY] == 'P'){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}