[Programmers/JAVA] 거리두기 확인하기

https://programmers.co.kr/learn/courses/30/lessons/81302?language=java 

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

풀이

 

해당 문제는 응시자가 앉아있는 위치에서 가까운 곳부터 탐색해야하기 때문에 BFS를 이용하여 문제를 풀었다.

(아직 능숙하게 풀기에는 멀은 것 같다 ...ㅠ)

 

1. 응시자(P)가 앉아있는 위치를 찾는다.

2. 응시자의 위치부터 탐색한다.

3. 응시자 인근 2이하에 P가 있으면 false,

- 파티션(X)가 있다면 더이상 보지않고 패스! (거리두기 성공)

- 빈테이블(O)가 있다면 빈테이블부터 다시 탐색시작! 맨해튼거리가 2보다 작은 것만 탐색한다. (그 이후는 거리두기 성공)

 

정리를 하자면

➡️ 응시자에서부터 맨해튼거리가 1인곳에 P가 없고, 맨해튼거리가 2인 곳에 O가 오고, O로 부터 맨해튼거리가 1인 곳에 P가 없다면 true를 반환하여 1을 저장한다. 

 

코드

class Solution {
	
	int[] dx = {1,-1,0,0};
	int[] dy = {0,0,-1,1};
	
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        for(int i=0;i<places.length;i++) {
        	// 거리두기 성공 여부저장
        	answer[i]=isTrue(places[i]);
        }
        return answer;
    }
    
    public int isTrue(String[] map) {
    	for(int i=0;i<map.length;i++) {
    		for(int j=0;j<map[i].length();j++) {
    			if(map[i].charAt(j)=='P') {
    				if(!bfs(map, i,j)) return 0;	// 거리두기 실패
    			}
    		}
    	}
    	return 1;
    }
    
    public boolean bfs(String[] map, int x, int y) {
    	Queue<Node> q = new LinkedList<>();
    	boolean[][] visited = new boolean[map.length][map.length];
    	q.offer(new Node(x,y));
    	visited[x][y]=true;
    	
    	while(!q.isEmpty()) {
    		Node node = q.poll();
    		
    		for(int i=0;i<4;i++) {
    			int new_x = node.x+dx[i];
    			int new_y = node.y+dy[i];
    			int manhattan = Math.abs(x-new_x) + Math.abs(y-new_y);
    			
    			if(new_x < 0 || new_y < 0 || new_x >= map.length || new_y >= map.length) continue;
    			// 범위를 벗어났을 때
    			if(visited[new_x][new_y] || manhattan > 2) continue;
    			// 방문했거나 맨해튼거리가 3이상이면 패스
    			
    			visited[new_x][new_y] = true;
    			if(map[new_x].charAt(new_y)=='X') continue;
    			// 파티션있으면 패스
    			else if(map[new_x].charAt(new_y)=='P') return false;
    			// 응시자가 있으면 거리두기 실패
    			else q.offer(new Node(new_x, new_y));
    			// 빈테이블이 있으면 다시 탐색시작!
    		}
    	}
    	return true;
    }
    
    public class Node {
    	int x;
    	int y;
    	
    	public Node(int x, int y) {
    		this.x=x;
    		this.y=y;
    	}
    }
}