-
[프로그래머스] 거리두기 확인하기 c++Coding Test/programmers 2022. 10. 12. 10:59728x90
문제 설명
- 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
- 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
- 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
※ 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다.
제한 사항
- places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다.
- places의 열 길이(대기실 세로 길이) = 5
- places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자리를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다.
- 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
- return 값 형식
- 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
- places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
- 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
입출력 예
places result [["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] 풀이
2중 for문으로 풀면 될 것 같지만 vector<vector<string>> 의 string도 문자 하나하나 검사해야하기 때문에
결국 이 문제는 삼중 for문으로 접근하는 문제이다.
#include <string> #include <vector> #include <queue> using namespace std; struct point{ int x = 0, y = 0, cnt = 0; point(int a, int b, int c){ x = a, y = b, cnt = c; } }; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; bool BFS(int a, int b, vector<string> vec){ vector<vector<bool>> visit(5, vector<bool>(5, false)); queue<point> Q; Q.push(point(a, b, 0)); visit[a][b] = true; while(!Q.empty()){ int x = Q.front().x; int y = Q.front().y; int Cnt = Q.front().cnt; Q.pop(); if(Cnt == 2) continue; for(int i = 0; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5){ if(visit[nx][ny] == false){ if(vec[nx][ny] == 'O'){ visit[nx][ny] = true; Q.push(point(nx, ny, Cnt + 1)); } else if(vec[nx][ny] == 'P'){ return false; } } } } } return true; } int CheckValue(vector<string> vec){ for(int i = 0; i < vec.size(); i++){ for(int j = 0; j < vec[i].size(); j++){ if(vec[i][j] == 'P'){ if(BFS(i, j, vec) == false){ return 0; } } } } return 1; } vector<int> solution(vector<vector<string>> places) { vector<int> answer; for(int i = 0; i < places.size(); i++){ answer.push_back(CheckValue(places[i])); } return answer; }
다른 풀이
#include <string> #include <vector> #include <iostream> using namespace std; bool is_valid_place(const vector<string>& place) { constexpr size_t N = 5; vector<vector<int>> is_in_use(N, vector<int>(N, false)); int di[] = {1,-1,0,0}; int dj[] = {0,0,1,-1}; for(size_t i=0; i!=N; ++i) for(size_t j=0; j!=N; ++j) if(place[i][j] == 'P'){ for(size_t k=0; k!=4; ++k){ size_t moved_i = i + di[k]; size_t moved_j = j + dj[k]; if(moved_i >= N || moved_j >= N) continue; switch(place[moved_i][moved_j]){ case 'P': return false; case 'O': if(is_in_use[moved_i][moved_j]) return false; is_in_use[moved_i][moved_j] = true; break; case 'X': break; } } } return true; } vector<int> solution(vector<vector<string>> places) { vector<int> answer(5); for(size_t i=0; i!=5; ++i) answer[i] = is_valid_place(places[i]); return answer; }
728x90'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 귤 고르기 c++ (0) 2022.11.24 [프로그래머스] 과일 장수 c++ (0) 2022.11.11 [프로그래머스] 모음사전 c++ (0) 2022.10.11 [프로그래머스] 할인 행사 c++ (2) 2022.10.11 [프로그래머스] 빛의 경로 사이클 c++ (2) 2022.10.04