알고리즘 풀이/프로그래머스

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

데롱디롱 2021. 9. 9. 17:14
728x90
맨 하단에 전체 코드가 있습니다.

 

 

[ 문제 풀이 ]

- 대기실의 모든 자리를 탐색하면서 모든 P를 찾는다.

- 모든 'P'에 대해서 거리두기를 만족하는지 확인한다.    => bfs이용!!

바로 옆에 'P'가 오지 않거나
바로 옆에 'O'가 있고, 'O'와 인접한 자리에 'P'가 없는 경우     => true

 

 

 

 

[ 풀이 방법 ]

1. 대기실의 모든 자리를 탐색하면서 'P'(응시자가 앉아있는 자리)를 찾는다.

 

 

2. bfs(사방탐색)를 돌면서, 맨해튼 거리 2 이내에 P가 또 있는지 확인한다.

 

 

 

- 거리두기를 지키기 위해서, 1번 자리에 와도 되는 것은 'O'와 'X'이다.
    => 'P'가 온다면, return false

if (p[nr].charAt(nc) == 'P')
       return false;

 

 

 

 

- 1번 자리에, 'X'가 있다면?!
     => 파티션으로 막혀있는 것 이므로, 
           2번자리에 무엇이 오든 상관이 없으므로 더이상 신경쓰지 않는다!!!

     => 사방탐색을 더 할 필요가 없음!!

 

 

 

 

- 1번 자리에, 'O'가 있다면?!
     => 2번자리에 'P'는 올 수 없고, 'X'와, 'O'는 가능하다.

     => queue에 현재, O의 위치를 넣어주어 다시 사방탐색을 진행한다!!!

 

 

 

 

 단, 다음에 사방탐색을 진행할 곳이 맨해튼 거리가 2인 곳에 대해서만 진행한다.
     => 맨해튼 거리 2가 넘는 곳에는 무엇이 와도 상관이 없기 때문!

int d = Math.abs(nr - r) + Math.abs(nc - c);     // 맨해튼 거리

// 다음 탐색을 하면, 맨해튼거리가 1 증가할 것이므로 d<2인 칸에 대해서만 탐색!
if (p[nr].charAt(nc) == 'O' && d < 2)  
       queue.offer(new int[] { nr, nc });

 

 

 


이때, 최초 출발점 'P'는 탐색 할 필요가 없으므로 제외한다.

int nr = position[0] + dr[i];
int nc = position[1] + dc[i];

if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5 || (nr == r && nc == c))       // 원래 출발점 P는 탐색 제외
       continue;

 

 

3. 모든 'P'점에 대해서 다음을 만족하면, true를 리턴한다.

     - 1번 자리에 'P'가 오지 않고

     - 1번 자리에 'O'가 있고, 사방에 인접한 2번 자리에 'P'가 없다면

 

 

 

 

[ 전체 코드 ]

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static int[] solution(String[][] places) {
        int[] answer = new int[places.length];

        for (int i = 0; i < places.length; i++) {
            String[] p = places[i];

            boolean isOk = true;
            for (int r = 0; r < 5 && isOk; r++) {
                for (int c = 0; c < 5 && isOk; c++) {
                    if (p[r].charAt(c) == 'P') {
                        if (!bfs(r, c, p))
                            isOk = false;
                    }
                }
            }
            answer[i] = isOk ? 1 : 0;
        }

        return answer;
    }

    private static boolean bfs(int r, int c, String[] p) {
        int dr[] = { -1, 1, 0, 0 };
        int dc[] = { 0, 0, -1, 1 };

        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] { r, c });

        while (!queue.isEmpty()) {
            int[] position = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nr = position[0] + dr[i];
                int nc = position[1] + dc[i];

                if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5 || (nr == r && nc == c))
                    continue;

                int d = Math.abs(nr - r) + Math.abs(nc - c);

                if (p[nr].charAt(nc) == 'P' && d <= 2)
                    return false;
                else if (p[nr].charAt(nc) == 'O' && d < 2)
                    queue.offer(new int[] { nr, nc });
            }
        }

        return true;
    }
}

 

 

프로그래머스 풀면서, 11점은 처음 받아봐서....

기념으로 찍어보았습니닷 ㅎㅎ 😃

 

 

 

이상한 점이나 질문이 있다면
댓글부탁드려요 :)
저작자표시