[Lv.2] 거리두기 확인하기 : Java

프로그래머스

 

 

 

이해하기

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

모든 P에 대해서 거리두기를 만족하는지 확인한다.

BFS 이용하기!

 

 

문제풀이

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

2. BFS를 돌리며 맨해튼 거리 2 이내에 P가 또 있는지 확인한다.

		2
	2	1	2
2	1	P	1	2
	2	1	2
		2

 

거리두기를 지키기 위해 1번 자리에 와도 되는 것은 'O'나 'X'이다.

 

• 1번 자리에 'P'가 온다면 ? false
• 1번 자리에 'X'가 온다면? 막혀있는 것이므로 2번 자리에 무엇이 와도 상관 없음 → BFS 중지
• 1번 자리에 'O'가 온다면? 2번 자리에 'P'가 있으면 안 됨, 'O'나 'X'는 가능 → 현재 위치에서 다시 BFS 
  • 단 맨해튼 거리가 2인 곳에 대해서만 진행
  • 최초 출발점은 제외

 

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

• 1번 자리에 'P'가 없음
• 1번 자리에 'O'가 있고, 사방에 인접한 2번 자리에 'P'가 없음

 

import java.util.*;

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 j = 0; j < 5 && isOK; j++) {
                for (int k = 0; k < 5 && isOK; k++) {
                    if (p[j].charAt(k) == 'P') {
                        if (!bfs(j, k, p)) {
                            isOK = false;
                        }
                    }
                }
            }

            answer[i] = isOK ? 1 : 0;
        }

        return answer;
    }

    public static boolean bfs(int j, int k, String[] p) {
        int[] dj = {-1, 1, 0, 0};
        int[] dk = {0, 0, -1, 1};

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

        while (!queue.isEmpty()) {
            int[] position = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nj = position[0] + dj[i];
                int nk = position[1] + dk[i];

                if (nj < 0 || nj >= 5 || nk < 0 || nk >= 5 || (nj == j && nk == k)) {
                    continue;
                }

                int d = Math.abs(nj - j) + Math.abs(nk - k);

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

 

 

solution 함수

int[] answer = new int[places.length];

 

place의 개수만큼 answer 배열 만들기

프로그래머스 예시에서는 대기실이 5개니 answer 배열의 크기는 5

 

for (int i = 0; i < places.length; i++) {
	String[] p = places[i];
 
	boolean isOK = true;
	for (int j = 0; j < 5 && isOK; j++) {
		for (int k = 0; k < 5 && isOK; k++) {
			if (p[j].charAt(k) == 'P') {
				if (!bfs(j, k, p))
				isOK = false;
			}
		}
	}
	answer[i] = isOK ? 1 : 0;
}

 

대기실 하나씩을 String[] p 배열에 할당

for문을 2번 돌며 각 자리마다 확인

만약 그 자리가 'P'라면 bfs 함수를 실행

bfs의 결과가 false이면 isOK = false

 

isOK가 true면 1, false면 0

 

bfs 함수

int dj[] = { -1, 1, 0, 0 };
int dk[] = { 0, 0, -1, 1 };

 

j와 k를 움직일 방향, 조합하면(-1, 0), (1, 0), (0, -1), (0, 1)이 됨

 

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

 

int[] 배열을 갖는 queue를 생성하고 {j, k} 방향을 offer

 

while (!queue.isEmpty()) {
	int[] position = queue.poll();
	for (int i = 0; i < 4; i++) {
		int nj = position[0] + dj[i];
		int nk = position[1] + dk[i];

		if (nj < 0 || nj >= 5 || nk < 0 || nk >= 5 || (nj == j && nk == k)) {
			continue;
		}

		int d = Math.abs(nj - j) + Math.abs(nk - k);

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

 

queue가 비어있지 않으면 while문 계속 돌림

 

for문을 4번 돌며 (방향이 4개라서) nj, nk를 이동

만약 nj와 nk가 0보다 작거나 5 이상일 경우 혹은 원래의 좌표인 j, k와 같을 경우에는 continue 하여 for문 첫 줄로 돌아감

 

아니라면 d (맨해튼 거리) 계산

 

만약 p[nj].charAt(nk)의 값이 'P' 이고 d가 2 이하이면 맨해튼 거리 내에 사람이 앉아있는 것이니 false를 리턴

또는 만약 p[nj].charAt(nk)의 값이 'O'이고 d가 2 미만이면 {nj, nk}를 새로운 기준 좌표로 삼아 다시 이동함

 

다 돌렸는데도 맨해튼 거리 내에 사람이 존재하지 않았다면 true를 리턴

 

 

 

 

bfs 문제는 아직도 너무 어렵다...

알고리즘 공부를 좀 더 해야할 것 같다🥹

 

---

 

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