[프로그래머스/Level2] 거리두기 확인하기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• BFS / DFS

1. 응시자가 있는 자리 P에서 BFS를 수행한다.

- 해당 응시자 위치에서 4방향 탐색 시 격자 범위를 벗어나고, 출발점 P인 경우 탐색하지 않는다.

if(!inRange(nx, ny) || (nx == x && ny == y))    continue;

 

- 맨해튼 거리 2 이하인 곳에 또 다른 응시자P가 존재한다면, 거리두기 실패

- 맨해튼 거리가 2 미만이고, 빈 테이블이 존재하는 경우, 큐에 다음 탐색 위치를 추가해 마저 탐색한다.

if(s[nx].charAt(ny) == 'P' && dist <= 2)    // 맨해튼 거리 2 이내에 P가 또 있다면 거리두기 실패
    return false;
else if(s[nx].charAt(ny) == 'O' && dist < 2)
    q.add(new int[] {nx, ny});

 

 

2. 모두 거리두기를 지키고 있다면, 정답 배열의 해당 인덱스 위치에는 1을 넣는다. 지키고 있지 않다면, 0을 넣는다. → boolean형 변수로 표시

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for(int k = 0 ; k < 5 ; k++) {
            String[] str = places[k];
            boolean isOk = true; // 모두 거리두기를 지키고 있는지 확인하는 변수
            
            for(int i = 0 ; i < 5 ; i++) {
                for(int j = 0 ; j < 5 ; j++) {
                    if(places[k][i].charAt(j) == 'P') { // 응시자가 있는 자리에서 bfs 수행
                        if(!bfs(i, j, str))
                            isOk = false;
                    }
                }
            }
            
            answer[k] = isOk ? 1 : 0;                
        }
        
        return answer;
    }
        
    private static boolean bfs(int x, int y, String[] s) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny) || (nx == x && ny == y))    continue;   // 출발점 P는 탐색 제외
                
                int dist = (int)Math.abs(r1 - r2) + (int)Math.abs(c1 - c2);   // 맨해튼 거리 계산
                
                if(s[nx].charAt(ny) == 'P' && dist <= 2)    // 맨해튼 거리 2 이내에 P가 또 있다면 거리두기 실패
                    return false;
                else if(s[nx].charAt(ny) == 'O' && dist < 2) // 빈 책상이 있을 때, 거리가 2 미만이면 마저 탐색
                    q.add(new int[] {nx, ny});
            }
        }
        
        return true;
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < 5 && 0 <= y && y < 5);
    }
}

 

 

➕ 다른 풀이 방식

DFS 방식 !

 

- 벽으로 막혀있으면 탐색 중단

- 사람이 있으면 거리두기 실패

- 책상이 있을 때, depth가 2보다 작으면 계속 탐색

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

---

💦 어려웠던 점

- 문자열을 어떻게 분리해서 활용할지의 문제...  2차원 char형 배열 만들어서 값 다시 저장하고 활용할 생각을 했었다. → 그냥 한 행씩 떼어다가 자유롭게 4방향 탐색도 가능하고 그렇다!

- 응시자 위치를 저장해두고, BFS를 한 번에 수행하려다가 머릿속에서 꼬여버렸다,, → 그냥 매 응시자 지점에서 BFS 수행하면 되었다.

 

 

1회독	2회독	3회독	4회독	5회독
V	240626

---

(참고)

[level2] 프로그래머스 - 거리두기 확인하기(JAVA)