29. LEVEL 2 - 거리두기 확인하기 - BFS

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

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

O는 이동이 가능한 통로, X는 이동할 수 없는 벽이라고 생각한다.

각 P마다 이동이 가능한 O를 따라서 2번 이동했을때 P를 만나면 false를 반환하면 된다.

각 P를 시작점으로 BFS를 사용해서 풀이할 수 있다.

 

import java.util.*;

class Solution {
    
    int[][] D = {
			{-1,0},		// 상
			{1,0},		// 하
			{0, -1},	// 좌
			{0,1}		// 우
	};
	
	class Node {	// 노드 클래스
		int row;    // 좌표
		int col;
		int dist;   // 맨해튼 거리
		
		public Node(int row, int col, int dist) {
			this.row = row;
			this.col = col;
			this.dist = dist;
		}		
	}
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];	// 결과 배열의 길이는 대기실 개수
        
        for (int i = 0; i < answer.length; i++) {	// 대기실을 하나씩 검사
			if(check(places[i])) {
				answer[i] = 1;	// i 대기실이 거리두기를 지키면 1
			}else {
				answer[i] = 0;	// i 대기실이 거리두기를 안지키면 0
			}
		}
        return answer;
    }
    
    public boolean check(String[] places) {	// places는 대기실 하나 
		
		for (int i = 0; i < places.length; i++) {
			for (int j = 0; j < places.length; j++) {
				if(places[i].charAt(j) == 'P') {
					if(!bfs(i, j, places)) {
						return false;
					}
				}
			}
		}		
		return true;		
	}
    
    public boolean bfs(int i, int j, String[] places) {
		Queue<Node> queue = new LinkedList<Node>();
		boolean[][] visit = new boolean[5][5];	// 방문체크
		
		queue.offer(new Node(i, j, 0));	// 시작 Node 넣기
		
		while(!queue.isEmpty()) {
			Node node = queue.poll();	// 큐에서 제거
			visit[node.row][node.col] = true;	// 방문체크					
			
			// 문제 처리
			if((node.dist == 1 || node.dist == 2) && places[node.row].charAt(node.col) == 'P') {				
				return false;   // 2회 이동 안에 P가 있으면 거리두기 안 지킴
			}
			
			// 이동하기
			for (int k = 0; k < 4; k++) {
				int nrow = node.row + D[k][0];	// 이동할 좌표 설정
				int ncol = node.col + D[k][1];
                
				if(nrow < 0 || nrow >= 5 || ncol < 0 || ncol >= 5) 
					continue;	// 범위를 벗어나며 이동 불가
				if(visit[nrow][ncol])
					continue;	// 방문했던 Node면 이동 불가
				if(places[nrow].charAt(ncol) == 'X')
					continue;	// 파티션이면 이동 불가				
				
				queue.add(new Node(nrow, ncol, node.dist + 1));
			}
		}
		return true;
	}
}