거리두기 확인하기(Java)

bearMin·2024년 3월 23일

🎯문제

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

대기실은 5개이며, 각 대기실은 5x5 크기입니다.

거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.

단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어,


위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다.	위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다.	위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다.

응시자가 앉아있는 자리(`P`)를 의미합니다.	빈 테이블(`O`)을 의미합니다.	파티션(`X`)을 의미합니다.

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다.
places의 열 길이(대기실 세로 길이) = 5
places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자리를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다.
입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
return 값 형식
- 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
- places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
- 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

places	result
`[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]`	[1, 0, 1, 1, 1]

입출력 예 설명

입출력 예 #1

첫 번째 대기실

No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

(0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
(1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
(4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

제한시간 안내

정확성 테스트 : 10초

※ 공지 - 2022년 4월 25일 테스트케이스가 추가되었습니다.

두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. ↩

✏️풀이

코드

import java.util.*;

class Solution {
	// bfs 탐색 메서드
    public boolean bfs(int x, int y, String[] p) {
        // x, y 좌표를 이동시키기 위한 배열
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        
        // 큐 생성
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{ x, y });
        
        // 큐에 값이 없을 때까지 반복
        while(!q.isEmpty()) {
            int nx = q.peek()[0];
            int ny = q.peek()[1];
            q.poll();
            
            for(int i = 0; i < 4; i++) {
                int mx = nx + dx[i];
                int my = ny + dy[i];
                
                // 범위 안에 들어오지 않았거나 같은 위치라면 continue
                if(mx < 0 || my < 0 || mx >= 5 || my >= 5 || (mx == x && my == y)) {
                    continue;
                }
                
                // 맨해튼 거리 구하기
                int d = Math.abs(mx - x) + Math.abs(my - y);
                
                // 거리두기에 실패했다면
                if(p[mx].charAt(my) == 'P' && d <= 2) {
                    return false;
                }
                // 더 탐색이 필요하다면
                else if(p[mx].charAt(my) == 'O' && d < 2) {
                    q.offer(new int[]{ mx, my });
                }
            }
        }
        
        return true;
    }
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        // 대기실 개수만큼 반복
        for(int i = 0; i < answer.length; i++) {
        	// 대기실 하나를 가져옴
            String[] p = places[i];
            
            // 기본값을 true로 설정
            boolean flag = true;
            for(int x = 0; x < 5 && flag; x++) {
                for(int y = 0; y < 5 && flag; y++) {
                	// 응시자가 있다면
                    if(p[x].charAt(y) == 'P') {
                    	// bfs 탐색을 진행
                        // 만일 탐색 중 false가 반환됐다면
                        if(!bfs(x, y, p)) {
                        	// flag를 false로 변경
                            flag = false;
                        }
                    }
                }
            }
            
            // flag가 true라면 1을 false라면 0을 저장
            answer[i] = flag ? 1 : 0;
        }
        
        return answer;
    }
}

설명

bfs 탐색을 사용해서 진행하였다.

응시자의 위치와 대기실을 매개변수로 받아온다. 탐색을 진행하기 위해 x, y 좌표를 이동시켜야하는데 이때 사용할 dx, dy 배열을 선언해준다.

bfs 탐색은 큐를 사용해서 진행한다. 따라서 큐를 생성한 뒤에 초깃값인 x, y를 int[]형으로 저장해준다.

큐에 값이 없을 때까지 반복을 진행하며 큐의 값을 하나 가져와서 위치를 옮겨가면서 탐색을 진행한다. 만일 이동한 위치가 대기실의 범위 안에 들어오지 않았거나 초깃값과 동일할 경우 continue를 사용해서 다음 탐색으로 넘어가준다. 그렇지 않다면 맨해튼 거리를 구해준다. |r2 - r1| + |c2 - c1|을 구현하기 위해 Math.abs 함수를 사용했다.

맨해튼 거리 안에 다른 응시자가 있다면 false를 반환해준다. 만약 빈자리라면 한번 더 탐색이 필요하므로 해당 값을 큐에 넣어준다.

이렇게 모든 탐색이 끝났을 때 false로 반환되지 않았다면 거리두기를 잘 지키고 있다는 뜻이므로 true를 반환해준다.

solution 메서드에서는 대기실의 개수만큼 answer 배열을 생성한다. 이후 반복문 역시 대기실의 개수만큼 반복을 진행한다.

String[] p에 대기실 하나를 가져오고 flag를 true로 설정해준다. 대기실을 탐색하면서 응시자가 있다면 해당 위치에서 bfs 탐색을 진행하여 거리두기를 지키고 있는지 확인한다. 만일 false가 반환됐다면 flag 역시 false로 설정한다. 대기실의 모든 탐색이 끝나면 다음 대기실의 탐색으로 넘어가기 전에 flag에 따라 answer[i]에 값을 넣어준다.

위의 모든 반복문을 진행한 뒤에 answer 배열을 반환해주면 문제를 해결할 수 있다!

💡느낀 점

bfs 탐색을 진행하지만 visit 배열을 사용하지 않는 방식으로 진행을 하였다. 기존의 bfs와 살짝 다르지만 탐색의 방식은 동일하기 때문에 bfs 탐색에 대해서 잘 알고 있다면 쉽게 풀 수 있는 문제라고 생각했다. 프로그래머스 문제들 중에서도 bfs, dfs 탐색이 매우 많이 나오는 것 같은데 코테 준비할 때 필수적으로 알아야하는 알고리즘들이라는 생각이 들어서 조금 더 확실하고 빠르게 사용할 수 있도록 공부해봐야겠다..