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

문제

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

프로그래머스

대기실 현황을 받아 사용자 간의 거리가 2 초과인지 확인하는 문제였다.

 

문제 풀이

중간에 코어덤프가 나서 많은 고민을 했다.. checkDistance()에서 사용자를 checkPoint에 담은 후 체킹했다는 표시를 남겼어야 헀는데 그러지 않아 dfs()에서 그 위치를 계속해서 탐색하게 되어 일어난 일이었다.  체킹하는 사용자 위치를 3으로 바꿔주었더니 해결됐다.

 

먼저 string으로 들어온 places를 잘라 int형 배열 map에 저장하고 각 map의 거리두기 현황을 체크했다. 체크하는 것은 일반적인 dfs 문제와 같은 방법으로 해결했다.

 

비쥬얼 스튜디오에서 이런일이 생기면 디버깅을 해서 쉽게 알아낼 수 있는데, 프로그래머스는 실행 결과만 볼 수 있어서 이런점이 어려운 것 같다. 이번에도 배열에서는 딱히 코어덤프 날 일이 없는데 코어덤프가 나서 당황했는데 재귀함수가 무한으로 돌아가는 상황도 항상 숙지해두고 조심해야겠다. 휴~

#include <string>
#include <vector>

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

vector<vector<int>> map(5,vector<int>(5)); //0빈자리 1파티션 2사용자
pair<int,int> checkPoint; //비교할 사용자 위치
int flag = 0;

void printMap(){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int isInside(int x,int y){ //map 안인지 확인
    if(x < 5 && x >= 0 && y < 5 && y >= 0) return 1;    
    else return 0;
}

int calManDistance(int x,int y){ //맨해튼 거리 계산
    int mx = checkPoint.first - x;
    int my = checkPoint.second - y;
    if(mx < 0) mx = -mx;
    if(my < 0) my = -my;
    
    return mx+my;
}

void dfs(int x,int y){
    if(flag == 1 || isInside(x,y) == 0 || calManDistance(x,y) > 2) return;
    
    for(int i=0;i<4;i++){ //4방향 확인
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(isInside(nx,ny) == 1 && calManDistance(nx,ny) <= 2){
            if(map[nx][ny] == 0){ //빈자리, 계속 탐색
                if(calManDistance(nx,ny) == 2) continue;
                dfs(nx,ny);
            }
            else if(map[nx][ny] == 2){ //사용자
                
                //printf("사용자 위치: (%d, %d)\n", nx, ny);
                flag = 1;
                break;
            }
            
        }        
    }
}

int checkDistancing(){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(map[i][j] == 2){ //사용자일 경우 체크
                checkPoint = {i,j};
                map[i][j] = 3;
                //printf("checkPoint: %d, %d\n",i,j);
                dfs(i,j);
                if(flag == 1){ //거리두기 안지킴
                    //printf("거리두기 안지킴\n");
                    return 0;                    
                }
            }
        }
    }
    //printf("거리두기 지킴\n");
    return 1;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    //1. 배열로 옮기기
    for(int i=0;i<5;i++){ //각 대기실
        flag = 0;
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++){
                if(places[i][j][k] == 'P'){ //사용자
                    map[j][k] = 2;
                }
                else if(places[i][j][k] == 'O'){ //빈자리
                    map[j][k] = 0;
                }
                else if(places[i][j][k] == 'X'){ //파티션
                    map[j][k] = 1;
                }
            }
        }
        //printMap();
        //각 대기실마다 거리두기 확인
        int result = checkDistancing();
        answer.push_back(result);
    }

    return answer;
}