[LV2] 거리두기 확인하기

1. 문제

1) 문제 링크

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

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

 

2) 설명

면접장(5 by 5)에서 면접자들이 맨해튼거리(가로 길이 + 세로 길이) 기준 2 이상 떨어져 앉아있을 때 거리두기를 지킨 것.

맨해튼거리가 2이하여도 그 사이에 파티션이 있다면 거리두기를 지킨 거다

places(면접장 배열)이 주어지면 각 place(면접장)이 거리두기를 지켰는지(1) 안 지켰는지(0)를 배열로 리턴하는 문제

참고  

- 면접자 : P

- 파티션 : X

- 빈자리 : O

2. 풀이

1) 알고리즘

    : 시뮬레이션(BFS)

 

2) 풀이 설명

- 첫 시도!

BFS를 사용해 풀이를 시도했다.

isFar 함수를 통해 각 place(면접장)이 거리두기가 지켜졌는지 확인한다.

P의 좌표들을 모두 큐에 삽입한다

큐가 빌 때까지 c(거리)가 2 이하이고 해당 P에서 방문한 적이 없는(visited[nx][ny]가 v(탐색 시작한 P의 idx)와 다른) 좌표들의 visited값을 v로 업데이트해준다

다음의 경우 visited[2, 2] 에서 1, 2가 다르기 때문에 그냥 2로 업데이트해주면 되는 거다

		visited 배열
1	1	1		2
1	P(idx=1)	1	2	2
1	X	1 2	2	P(idx=2)
X	X		2	2
P(idx=3)	3	3		2

 

만약 다음과 같이 P를 발견하면 return false 해준다

		visited 배열
1	1	1		2
1	P(idx=1)	1	2	2
1	X	2	2	P(idx=2)
X	X		2	2
				P(idx=3)

 

 

사실 P가 있냐 없냐만 보면 되는데 왜 visited 배열을 썼는가 하면 같은 자리를 두 번 이상 방문하지 않도록 하기 위해서다. 예를 들어 [0, 0]은 P(idx=1)이 좌 -> 상 이동, 상 -> 좌 이동 두 번 방문해야하는데 이때 visited배열을 보고 visited[0][0](=1) 과 v(=1)이 같기 때문에 더 방문하지 않도록 하는 것이다.

 

풀고나서 4개짜리 tuple을 썼다는 게 마음에 안 들었는데 찾아보니 더 간단한 방법이 있었다!

 

- 두 번째 시도!

사실 두 번째 풀이의 핵심은 한 면접자당 BFS를 1 depth까지만 탐색하는 거였다.

i번째 면접자가 방문한 자리를 다른 면접자가 방문한다면 이건 올바르지 않은 거리두기를 하게 된 것이다

설명하자면 교점을 기준으로 보았을 때 [x, y] 교점으로부터 거리가 1인 면접자가 둘 이상 있다면 그 면접자들 간의 거리는 2 이하가 되기 때문이다

예를 들어 다음과 같은 경우에 [4, 3]자리를 P(idx=2)가 방문했는데 P(idx=3)이 또 방문한다면 이 둘은 거리가 2 이하기 때문에 return false 해주면 된다

 

		visited 배열
	1
1	P(idx=1)	1		2
	X		2	P(idx=2)
				2 3
				P(idx=3)

 

 

3. 코드

첫 번째 방법

//BFS 탐색을 2 depth까지 하는 비효율적인 방식의 첫 시도
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

bool isFar(const int boardSize, vector<string> place, vector<vector<int>> &visited){
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1};
    
    queue<tuple<int, int, int, int>> q;
        
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<boardSize;j++){
            if(place[i][j] == 'P')
				q.push({i, j, 0, q.size()});
        }
    }
	while(!q.empty()){
      	int x = get<0>(q.front());
        int y = get<1>(q.front());
        int c = get<2>(q.front()); // 거리
        int v = get<3>(q.front()); // 탐색 중인 면접자의 index
        q.pop();
        
        visited[x][y] = v;
        
        for(int d=0;d<4;d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            int nc = c + 1;
                
            if(nx<0 || nx>=boardSize || ny<0 || ny>=boardSize
            	|| visited[nx][ny]==visited[x][y] // 탐색 중인 면접자가 방문한 적이 있다면 continue
               	|| place[nx][ny]=='X' // 파티션이면 continue
              	|| nc>2) // 다음에 갈 자리가 맨해튼 거리 2 초과면 continue
            	continue;
            
            if(place[nx][ny] == 'P')
                return false;
            q.push({nx, ny, nc, v});
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
    const int boardSize = 5;
	vector<vector<int>> visited(boardSize, vector<int>(boardSize, -1));
	
    for(auto place : places)
		answer.push_back(isFar(boardSize, place, visited));
    
	return answer;
}

 

두 번째 방법

//1 depth BFS 탐색을 통한 효율적인 방법
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

bool isFar(const int boardSize, vector<string> place){
    const vector<int> di = {-1, 1, 0, 0};
    const vector<int> dj = {0, 0, -1, 1};
    
    vector<vector<bool>> visited(boardSize, vector<bool>(boardSize, false));
        
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<boardSize;j++){
            if(place[i][j] == 'P'){
                visited[i][j] = true;
            	for(int d=0;d<4;d++){
                    int ni = i + di[d];
            		int nj = j + dj[d];
                    if(ni<0 || ni>=boardSize || nj<0 || nj>=boardSize || place[ni][nj]=='X')
                        continue;
                    if(visited[ni][nj])
                        return false;
                    visited[ni][nj] = true;
                }    
            }
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
    const int boardSize = 5;
	
    for(auto place : places)
		answer.push_back(isFar(boardSize, place));
    
	return answer;
}

4. 느낀점

내 생각에는

엄청 길지는 않은 시간에

엄청 느리지는 않은 알고리즘으로

엄청 가독성 떨어지지는 않는 코드로

성공은 했지만 다 최선의 방법은 아니었다ㅠㅠ

면접자가 중심이라 생각해서 면접자를 기준으로만 생각했는데 교점을 기준으로 생각했으면 좋았을 텐데 아쉬웠다...

보이지 않는 걸 보는 연습이 필요한 것 같다..!