[2021 카카오 채용연계형 인턴십] 거리두기 확인하기 - JAVA

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

프로그래머스

---

이 문제는 bfs를 사용하여 탐색해서 풀면 된다!

1. 대기실의 모든 자리를 탐색하면서 모든 'P'를 찾는다
2. 모든 'P'에 대해서 거리두기를 만족하는지 확인한다 -> bfs 이용

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

 

 

[풀이 방법]

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

• 이는 반복문을 사용하여 문자열 비교를 통해 찾으면 된다!

 

 

2. bfs를 사용하여 사방을 탐색하면서, 맨해튼 거리 2 이내에 또 다른 'P'가 있는지 확인한다

• 'P'의 주변에 1 자리에 올 수 있는 것은 'O' 또는 'X'이다
• 만약 'P'가 1 자리에 온다면, false를 반환한다!

if(place[nx].charAt(ny) == 'P) {
	return false;
}

 

 

1번 자리에 'X'가 온 경우

• 만약 1번 자리에 'X'가 온 경우, 파티션으로 막혀있는 것이므로 2번 자리에 무엇이 오든 상관 없기 때문에 더이상 검사하지 않는다
• 즉, 사방 탐색(bfs)를 할 필요가 없다!

 

 

1번 자리에 O가 온 경우

• 1번 자리에 'O'가 온 경우, 2번 자리에 'P'는 올 수 없고, 'X' 또는 'O'만 가능하다
• 즉, queue에 현재 'O'의 위치를 넣어주어서 다시 사방 탐색(bfs)를 진행하면 된다!
• 단, 다음에 사방 탐색을 진행할 곳이 맨해튼 거리가 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'가 없는 경우

 

---

이제 전체 코드를 보면서 이해해보자!

 

[자바 코드]

package programmers;

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

public class CheckKeepDistance {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i=0;i<5;i++) {
            String[] place = places[i];
            boolean check = true;
            for(int j=0;j<5 && check;j++) {
                for(int k=0;k<5 && check;k++) {
                    if(place[j].charAt(k) == 'P') {
                        if(!bfs(j, k, place)) {
                            check = false;
                        }
                    }
                }
            }
            answer[i] = check ? 1 : 0;
        }
        return answer;
    }

    public boolean bfs(int x, int y, String[] place) {
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

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

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

            for(int i=0;i<4;i++) {
                int nx = position[0] + dx[i];
                int ny = position[1] + dy[i];

                if(nx<0 || ny<0 || nx>=5 || ny>=5 || (nx==x&&ny==y)) {
                    continue;
                }
                int distance = Math.abs(nx-x) + Math.abs(ny-y); //맨해튼 거리
                if(place[nx].charAt(ny) == 'P' && distance<=2) {
                    return false;
                } else if(place[nx].charAt(ny) == 'O' && distance<2) { // 다음 탐색을 하면, 맨해튼 거리가 1 증가하므로 d<2인 칸에 대해서만 탐색
                    queue.offer(new int[] {nx, ny});
                }
            }
        }
        return true;
    }
}

 

 

 

 

---

참고)

https://jisunshine.tistory.com/148

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

위 블로그를 참고하여 풀었습니다 :)