프로그래머스 - 거리두기 확인하기 [Java, Javascript]

 

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

프로그래머스

 

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

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

 

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

예시

 

 

풀이 

이 문제는 단순히 상하좌우를 확인하는 것이 아닌 맨해튼 거리가 2인 모든 위치를 확인해야 한다. 

A(r1, c1), B(r2, c2)가 있을 때 맨해튼 거리는 |r1 - r2| + |c1 - c2|로 측정한다. 

 

주목해야 할 점은 맨해튼 거리 2에 도달하기 위해서는 맨해튼 거리 1에 먼저 도달해야 한다는 것이다

. 

그리고 맨해튼 거리 1은 상하좌우를 나타낸다. 즉, 맨해튼 거리 1의 위치들이 파티션으로 막혀있다면 맨해튼 거리2는 다른 응시자가 있어도 파티션에 가로막히기 때문에 거리두기가 인정된다. 

방향 하나당 3개의 타일로 이동이 가능하며 중복되는 타일이 존재한다. 따라서 우리는 어떤 방향이 뚫려있을 경우 그 방향을 검사하도록 해야한다. 

 

하나의 대기실에 대한 흐름을 정리하면 다음과 같다.

 

1. 대기실의 모든 응시자 위치에서 반복
   1. 상하좌우 빈 테이블이 이쓴 방향에 대해 1-B로 진행
   2. 빈 테이블과 인접한 위치 중 응시자가 있다면 거리두기를 지키지 않은 것
2. 모든 응시자의 위치를 검사했으나 거리두기를 지키지 않은 경우를 발견하지 못했으면 거리두기를 지킨 것

코드작성

입력이 String[][] 형식으로 들어오고, 대기실 하나는 String[] 형식이 된다. 원소 하나하나를 관찰하고 검사할 것이므로 대기실을 char[][] 형태로 만든 후 거리두기 결과를 저장할 배열을 선언한다.

 

int[] answer = new int[places.length];
for (int i = 0; i < answer.length; i++) {
    String[] place = places[i];
    char[][] room = new char[place.length][];
    for (int j = 0; j < room.length; j++) {
        room[j] = place[j].toCharArray();
    }
    // 거리두기 검사 후 answer에 기록
}
return answer;

 

이제 하나의 대기실은 char[][]로 표현되었다. 이 대기실이 거리두기를 지키는지 검사하는 isDistanced() 메서드를 다음과 같이 선언한다. 

private boolean isDistanced(char[][] room) {
    //거리두기 검사
    return true
    }

 

다음으로 대기실에서 응시자가 앉아 있는 모든 위치에 대해 거리두기 검사를 진행해야 한다. 다음과 같이 응시자가 앉아 있지 않은 위치들은 continue; 키워드로 검사를 건너뛰게 한다.

 

private boolean isDistanced(char[][] room) {
    for(int y = 0; y < room.length; y++) {
        for(int x = 0; x < room[y].length; x++) {
            if(room[y][x] != 'P')   continue;
            //거리두기 검사
        }
    }
    return true
}

 

다음으로 해당 대기실에서 응시자의 위치 (x, y)가 거리두기를 지키는지 검사하는 메서드를 선언한다. 

 

private boolean isDistanced(char[][] room, int x, int y) {
    //room[x][y]가 거리를 지키는지 검사
    return true;
}

 

1.1 상하좌우 중 빈 테이블이 있는 방향에 대해 1.2로 진행

(x,y) 위치에 있는 응시자가 거리두기를 지키고 있는 지 검사하려면 먼저 상하좌우를 검사해야 한다. 

상하좌우를 검색하고자 다음과 같이 dx, dy를 선언해준다. 

 

private static final int dx[] = {0, 0, -1, 1};
private static final int dy[] = {-1, 1, 0, 0};

 

이제 dx, dy를 이용하여 상하좌우를 살펴볼 수 있다. 다음과 같이 상하좌우 위치를 가져오고, 해당 위치가 범위를 벗어나지 않는지 검사한다.

 

private boolean isDistanced(char[][] room, int x, int y) {
    for(int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length)  continue;
        //room[ny][nx]로 다른 응시자에게 도달할 수 있는 지 검사
    }
    return true;
}

 

room[ny][nx]는 3가지 속성을 지닌다.

 

• X: 파티션일 경우, 이 위치를 이용해서 다른 응시자에게 도달할 수 없으므로 별도의 처리가 필요하지 않음
• P: 응시자일 경우, 맨해튼 거리 1에 다른 응시자가 있는 것이므로 거리두기가 지켜지지 않은 것
• O: 빈 테이블일 경우, 인접한 곳에 다른 응시자가 있다면 거리두기가 지켜지지 않은 것

이는 다음과 같이 switch 문으로 구현할 수 있다.

 

switch(room[ny][nx]) {
    case 'P': return false;
    case 'O': 
        //인접한 테이블 검사
        break;
}

 

1.2 빈 테이블과 인접한 위치 중 응시자가 있다면 거리두기를 지키지 않은 것

여기서 인접한 곳이라 함은 다시 상하좌우를 의미한다. 하지만 원래 검사를 시작했던 응시자는 제외해야 하기 때문에 해당 방향으로는 검사를 시행하지 않아야 한다. 

 

따라서 검사를 제외할 방향도 함께 넘겨주어야 한다. 

 

private boolean isNextToVolunteer(char[] room, int x, int y, int exclude) {
    for (int d = 0; d < 4; d++) {
        if (d == exclude)   continue;

        int nx = x + dx[d];
        int ny = y + dy[d];
        if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length)  continue;
        if(room[ny][nx] == 'P') return true;
    }
    return false;
}

 

반대 방향을 어떻게 측정할 수 있을까? 이 문제에는 방향에 정답이 없다. 어떤 순서든 상하좌우를 탐색하기만 하면 된다.

그렇다면 다음과 같은 순서가 있을 수 있다.

상(0)좌(1)우(2)하(3)

상하는 총합 3을 가지며 좌우도 총합 3을 가진다. 따라서 우리는 다음과 같이 완성할 수 있다. 

 

private static final int dx[] = {0, -1, 1, 0};
private static final int dy[] = {-1, 0, 0, 1};

switch(room[ny][nx]) {
    case 'P': return false;
    case 'O': 
        if (isNextToVolunteer(room, x, y, 3-d)) return false;
        break;
}

 

최종 코드는 다음과 같다.

 

class Solution {
    private static final int dx[] = {0, -1, 1, 0};
    private static final int dy[] = {-1, 0, 0, 1};
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
       
        
        for (int i = 0; i < answer.length; i++) {
            String[] place = places[i];
            char[][] room = new char[place.length][];
            for (int j = 0; j < room.length; j++) {
                room[j] = place[j].toCharArray();
            }
            // 거리두기 검사 후 answer에 기록
            if(isDistanced(room)) {
                answer[i] = 1;
            }
            else {
                answer[i] = 0;
            }
        }
        return answer;
    }
    
    private boolean isDistanced(char[][] room) {
        for(int y = 0; y < room.length; y++) {
            for(int x = 0; x < room[y].length; x++) {
                if(room[y][x] != 'P')   continue;
                //거리두기 검사
                if(!isDistanced(room, x, y)) return false;
            }
        }
        return true;
    }
    private boolean isDistanced(char[][] room, int x, int y) {
        for(int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length)  continue;
        
            switch(room[ny][nx]) {
                case 'P': return false;
                case 'O': 
                    if (isNextToVolunteer(room, nx, ny, 3-d)) return false;
                    break;
            }
        }
        return true;
    }
    
    private boolean isNextToVolunteer(char[][] room, int x, int y, int exclude) {
        for (int d = 0; d < 4; d++) {
            if (d == exclude)   continue;
            
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length)  continue;
            if(room[ny][nx] == 'P') return true;
        }
        return false;
    }
}

 

다음은 자바스크립트 버전이다. 기본 내용은 동일하다.

 

class Solution {
    constructor() {
        this.dx = [0, -1, 1, 0];
        this.dy = [-1, 0, 0, 1];
    }

    function solution(places) {
        return places.map(place => {
            const room = place.map(row => row.split('')); // 문자열 배열을 2차원 배열로 변환
            return this.isDistanced(room) ? 1 : 0;
        });
    }

   function isDistanced(room) {
        for (let y = 0; y < room.length; y++) {
            for (let x = 0; x < room[y].length; x++) {
                if (room[y][x] !== 'P') continue;
                if (!this.isDistancedAt(room, x, y)) return false;
            }
        }
        return true;
    }

    function isDistancedAt(room, x, y) {
        for (let d = 0; d < 4; d++) {
            let nx = x + this.dx[d];
            let ny = y + this.dy[d];
            if (ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) continue;

            switch (room[ny][nx]) {
                case 'P': return false;
                case 'O':
                    if (this.isNextToVolunteer(room, nx, ny, 3 - d)) return false;
                    break;
            }
        }
        return true;
    }

    function isNextToVolunteer(room, x, y, exclude) {
        for (let d = 0; d < 4; d++) {
            if (d === exclude) continue;

            let nx = x + this.dx[d];
            let ny = y + this.dy[d];
            if (ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) continue;
            if (room[ny][nx] === 'P') return true;
        }
        return false;
    }
}