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

문제 내용

거리두기를 잘 지켜서 앉아있는지 확인하기 위한 코드를 구현하는 문제이다

제한사항을 보면, P는 사람 O는 빈테이블 X는 파티션이다

모든 값은 5X5로 주어지고, 어느 한 곳에서라도 거리두기가 지켜지지 않으면 0이 된다

처음에는 너비우선 탐색만 이용하였는데, 파라미터 전달이 너무 많고 가독성이 떨어져서

효율적인 코드 작성을 하기 위해 인터넷을 참조하여 여러 클래스와 메소드를 이용하였다 

사용한 클래스와 메소드 정리

1. isCorrect : 각 배열이 거리두기를 잘 지키고 있는지에 따라 값 리턴 - 0 or 1

2. bfs : 해당 배열의 특정 부분(P값)을 중심으로 조건에 따라 거리두기가 잘 지켜져 있는지 확인

3. Point : bfs에서 사용할 x, y값의 좌표를 담은 클래스 - 검사할 좌표를 담기 위해 생성

 

효율적인 방법을 사용하기 위해 BFS(너비우선탐색)을 이용하였다

문제 풀이 절차를 정리하였다

1. 5X5 배열 내에서 P가 나오면 해당 x,y 좌표와 배열전체를 bfs 메소드로 넘긴다

2. Point타입의 Queue 를 생성한 후, 가장 먼저 들어온 좌표부터 queue에 넣는다

3. while문으로 Queue가 빌 때까지(=해당 좌표 중심으로 검색 완료된 상태까지) 반복문 실행한다

※ 여기서 검사한 좌표는 isChecked[x좌표][y좌표] 값을 true로 바꿔준다

4. 상하좌우를 담은 배열 dx, dy의 값을 가져와 해당 좌표(x,y)에 더하여 검사한다 (총 4번)

5. 만약 P가 있으면 이미 거리두기가 지켜지지 않은 것이므로 false 리턴한다

6. 만약 O가 있으면 한칸 옆에 P가 있는지 확인하기 위해 Queue에 해당 좌표를 Point 객체로 넣어준다

※ O 중심으로 원래 좌표(x,y)는 이미 검사했기 때문에 isChecked 값이 true이므로 검사 안 함

7. queue에 있는 모든 좌표 검사가 무사히 끝났으면 true를 리턴한다

8. 반복 

 

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

public class Solution{
    public static int [] dx = {0,0,1,-1}; // 좌우 
    public static int [] dy = {1,-1,0,0}; // 상하
    public static boolean [][] isChecked;
	public static void main(String[] args){
		String[][] places= {{"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"}};
		int[] answer= new int[places.length];
		
		for(int i=0; i<places.length; i++) {
			answer[i]= isCorrect(places[i]);
		}
		
		for(int i : answer) {
			System.out.println(i);
		}
 
	}
	
	public static int isCorrect(String[] str) {
		for(int i=0; i<str.length; i++) {
			for(int j=0; j<str[i].length(); j++) {
				if(str[i].charAt(j)=='P')
					if(!bfs(i,j,str))
						return 0;
			}
		}
		return 1;
	}
	
	public static boolean bfs(int x, int y, String[] str) {
		Queue<Point> queue = new LinkedList<>();
		isChecked = new boolean[5][5];
		
		queue.offer(new Point(x,y));
		isChecked[x][y]=true;
		
		while(!queue.isEmpty()) {
			Point current = queue.poll();
			
			for(int i=0; i<4; i++) {
				int nx = current.x +dx[i];
				int ny = current.y +dy[i];
				int manhattan = Math.abs(x-nx)+Math.abs(y-ny);
				
				if(nx<0||ny<0||nx>=str.length||ny>=str.length) continue; //5X5 범위를 벗어나면 확인안함
				if(isChecked[nx][ny] || manhattan>2) continue;	// 체크한 곳이거나 맨해튼 거리가 2보다 크면 확인안함
				
				isChecked[nx][ny] = true;	// 방문했으므로 true로 바꿈
				if(str[nx].charAt(ny)=='X') continue; // X는 칸막이므로 체크 안해도 됨
				else if(str[nx].charAt(ny)=='P') return false;	//P의 옆이 P이면 거리두기 실패 & 바로 false 리턴
				else queue.offer(new Point(nx,ny));	// O인 경우 바로 옆에 P가 있는지 확인해야 함
			}
		}
		return true;
	}
	
	   public static class Point {
	        int x;
	        int y;
	        
	        public Point(int x, int y) {
	            this.x = x;
	            this.y = y;
	        }
	    }
}

 

 

[문제]

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