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

문제내용

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

코딩테스트 연습 - 거리두기 확인하기

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

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

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어,

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을 담습니다.

 

---

문제 접근 방법

일단 풀고 나서 느낀 건 전에 풀었던 알고리즘을 어느 정도 활용해 풀어내는 문제여서 그런지 재밌다고 느꼈다.

그리고 다 풀고 다른 분들이 푼 거를 블로그에서 봤는데 나와 비슷하게 풀었지만 좀 다른 건 다른 분은 상하좌우만 탐색하여 다음에 'P', 'O', 'X' 중 어떤 문자가 나오는지에 따라 경우를 나누고 BFS 방식으로 풀었는데
나는 상하좌우대각을 탐색하여 2거리내에 'P'가 나오는 경우를 기준으로 삼아 BFS 방식 비슷하게 문제를 풀었다.

따라서 이번 포스팅엔 내가 푼 방법을 설명하겠지만 다른 분의 코드가 좀 더 효율적이라 생각돼서 코드에는 내가 푼 것과 다른 분이 푼 코드를 넣어보겠다.

 

일단 내가 풀었던 풀이 방법은 간단하게 말하면 아래와 같다.

1. 대기실 분리
   우리에게 주어진 places 배열에는 5개의 대기실이 넣어져 있다. 하지만 우리는 대기실 하나씩 거리두기를 했는지 안 했는지 확인해야 하기 때문에 가장 먼저 대기실 한 개씩 분리해주는 작업을 했다.
   그리고 대기실이 하나씩 분리될 때마다 대기실이 거리두기를 했는지 안 했는지 검사하는 방식으로 코드를 작성했다.
2. 분리된 대기실에서 'P'(앉은 사람)이 나올 경우
   분리된 대기실을 처음부터 끝까지 탐색하면서 'P'가 나올 때마다 맨해튼 거리가 2 이하에 또 다른 'P'가 있는지 없는지 탐색해야 했다.
   이유는 또 다른 'P'가 나왔을 때 연속적으로 'P'가 있는지 혹은 'P'와 'P'사이에 다른 'O'나 'X'가 들어오는지에 따라 거리두기 준수 여부가 달라지기 때문에 탐색해야 했다.
3. 현재 앉아 있는 사람 'P'에 대해 거리두기 준수 여부 검사
   현재 앉아 있는 사람 'P'의 인덱스 (x, y)를 기준으로 하여 상하좌우 대각선에 'P'가 있을 때 거리두기가 됐는지 안됐는지 분리했던 대기실 배열을 처음부터 끝까지 검사한다.
   이때 상하좌우 대각선을 탐색하기 위해 BFS 알고리즘과 같은 방식으로 풀어냈다.

위 과정을 places에 입력돼있는 대기실의 개수만큼 반복하면서 3번에서 거리두기 준수 여부가 확인됐을 때 비로소 대기실 하나에 대해 0 or 1을 answer 배열에 places 배열을 전부 탐색하면서 하나씩 넣어준다. 

 

---

풀이

내 풀이

public class Solution{
	static int[] dx = {1, -1, 0, 0, 1, -1, 1, -1};//상하좌우대각
	static int[] dy = {0, 0, 1, -1, 1, -1, -1, 1};//상하좌우대각
	public static int[] solution(String[][] places) {
		int[] answer = new int[5];
		String[] waitRoom = new String[5];//대기실 배열
		
		//대기실 한개씩 분리
		for(int i=0; i<places.length; i++) {	
			for(int j=0; j<places[0].length; j++) {
				waitRoom[j] = places[i][j];
			}
			
			//i번째 대기실 거리두기 했으면 1, 안했으면 0 반환하는 메소드
			answer[i] = dis(waitRoom);
		}
		
		return answer;
	}
	
	//거리두기가 된 대기실인지 확인하는 메소드
	public static int dis(String[] waitRoom) {
		int ans = 0;
		char[][] mans = new char[5][5];//한개 대기실에 앉은 사람들의 배열
		
		//한개 대기실의 사람들을 5x5 배열에 넣음
		for(int i=0; i<waitRoom.length; i++) {
			mans[i] = waitRoom[i].toCharArray();
		}
		
		//'P'(앉은사람)이 나올경우 그사람에 대해서 거리두기 여부 탐색
		for(int i=0; i<mans.length; i++) {
			for(int j=0; j<mans.length; j++) {
				char posi = mans[i][j];
				//거리두기 안했으면 false, 이 대기실은 0 반환하게됨
				if(posi=='P' && !checkManHaTan(i,j,mans)) { 
					return ans;
				}
			}
		}
		
		ans = 1;
		return ans;
	}
	
	//(x,y)에 앉아 있는 사람에 대하여 상하좌우대각에 앉은사람이 거리두기 했는지 안했는지 체크
	public static boolean checkManHaTan(int x, int y, char[][] mans) {
		boolean ans = false;
		
		for(int i=0; i<8; i++) {
			if(i<=3) {//상하좌우 탐색할경우
				int oneX = x + dx[i];//상하좌우 거리가 1일때 인덱스
				int oneY = y + dy[i];//상하좌우 거리가 1일때 인덱스
				int twoX = x + (dx[i])*2;//상하좌우 거리가 2일때 인덱스
				int twoY = y + (dy[i])*2;//상하좌우 거리가 2일때 인덱스
				
				//상하좌우 거리가 1일때 'P'(앉은사람)가 또 있다면 거리두기 안한거 
				if(oneX>=0 && oneY>=0 && oneX<5 && oneY<5) {//배열밖으로 범위 초과하는지
					if(mans[oneX][oneY]=='P') {	return ans;	}
				}
				
				/*
				 * 상하좌우 거리가 2일때 'P'가 또 있고
				 * 상하좌우 거리가 1일때 'O'인 경우는 거리두기 안한거.
				 * 그외에는 거리가 1일때 'X'가 나오는 경우이며 이때는 거리두기 한거.
				 * 거리가 1일때 'P'가 나오는 경우는 위의 분기문에서 체크함.
				 */
				if(twoX>=0 && twoY>=0 && twoX<5 && twoY<5) {//배열밖으로 범위 초과하는지
					if(mans[twoX][twoY]=='P') {
						if(mans[oneX][oneY]=='O') { return ans; }
					}
				}
				
			}else {//대각선을 탐색할 경우
				int diaX = x + dx[i];//대각선 인덱스
				int diaY = y + dy[i];//대각선 인덱스
				
				//현재 (x,y)에 앉은 사람에 대하여 대각선에 앉은사람이 있을경우
				if(diaX>=0 && diaY>=0 && diaX<5 && diaY<5) {//배열밖으로 범위 초과하는지
					if(mans[diaX][diaY]=='P') {
						if(diaX>x && diaY>y) {//우하단에 앉은사람이 있을때
							if(mans[x+1][y]=='O' || mans[x][y+1]=='O') { return ans; }
						}else if(diaX>x && diaY<y) {//좌하단에 앉은사람이 있을때
							if(mans[x+1][y]=='O' || mans[x][y-1]=='O') { return ans; }
						}else if(diaX<x && diaY>y) {//우상단에 앉은사람이 있을때
							if(mans[x-1][y]=='O' || mans[x][y+1]=='O') { return ans; }
						}else {//좌상단에 앉은 사람이 있을때
							if(mans[x-1][y]=='O' || mans[x][y-1]=='O') { return ans; }
						}
					}
				}
			}
		}//for(상하좌우대각 탐색)
		
		//위의 탐색결과 return안됐으면 거리두기 한거라서 true 반환.
		ans = true;
		return ans;
	}
}

---

다른 사람 풀이

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;
    }
}

---

마치며

솔직하게 말하면 다른 사람 풀이가 좀 더 깔끔하고 효율이 좋다고 생각한다. 나도 BFS로 풀 생각을 했었고 상하좌우의 다음 문자가 나왔을 때 어떻게 처리해야 할지 고민하다가 그냥 전부 탐색한 거였는데 풀이를 보니 생각보다 간단하다고 느껴진다. 그래도 나는 잘 풀었다고 생각한다.