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

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

프로그래머스

---

 

[풀이 방법]

각 대기실의 자리 정보를 room 변수에 할당하고 다음을 반복

 

1. P인 자리를 찾는다

 

2. 해당 자리를 기준으로 탐색(동서남북) 시작

    💫탐색 종료조건1: 파티션을 만나는 경우 -> 탐색 종료 (파티션을 거쳐 가는 곳은 어떠한 값을 가져도 상관없기 때문)

    💫탐색 종료조건2: 거리가 2인 경우 -> 탐색종료 (거리가 2보다 크면 어떠한 값을 가져도 상관없기 때문)

    💫탐색 종료조건3: 값이 P인 경우 -> 거리두기를 준수하지 않았으므로 거리두기준수여부 변경하고 탐색 종료

    탐색 종료조건 중 해당 하는 경우가 없으면 다음과 같은 과정으로 탐색

    2-1) 다음 자리의 좌표를 구한다 (nx, ny)

    2-2) 다음 자리의 좌표가 범위를 벗어나거나 이미 방문한 좌표일 경우 방문하지 않고 다음 방향으로 이동

    2-3) 2-2의 경우가 아니라면 다음으로 이동하면서 거리 +1

 

[풀이 코드_Java] 

class Solution {
    
    int isTrue;           // 거리두기 준수 여부
    String[] room;
    boolean[][] visited;   
    
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for (int n = 0; n < 5; n++) {  // n: 대기실 번호
            // 거리두기 준수 여부와 room초기화
            isTrue = 1;
            room = places[n];
            
            for (int x = 0; x < 5; x ++) {
                for (int y = 0; y < 5; y++) {
                    visited = new boolean[5][5];  // 방문기록 초기화
                    if (room[x].charAt(y) == 'P') {
                        visited[x][y] = true;
                        checkSeat(x, y, 0);
                    }
                    if (isTrue == 0) break; // 거리두기 준수하지 않았을 경우 더 이상 탐색하지 않아도 됨
                }
                if (isTrue == 0) break; // 거리두기 준수하지 않았을 경우 더 이상 탐색하지 않아도 됨
            }
            answer[n] = isTrue;
        }
        
        return answer;
    }
    
    public void checkSeat(int x, int y, int dst) {
        
        if (dst != 0 && room[x].charAt(y) == 'P') { 
            isTrue = 0;
            return;
        }
        
        if (room[x].charAt(y) == 'X' || dst == 2) return; // 파티션이거나 맨하탄거리가 2일 경우 탐색 종료
        
        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 || visited[nx][ny]) continue;
            
            visited[nx][ny] = true;
            checkSeat(nx, ny, dst + 1);
        }
        
    }
}