[프로그래머스] 81302 거리두기 확인하기 (2021 카카오 인턴십)

1. 문제

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

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

2. 접근방법

1. 맵에서 p를 찾는다.

2. bfs로 거리가 2인 지역까지 탐색을 한다.

3. X를 만나면 가지치기

4. 다른 P를 만날경우 answer에 0입력

5. 위 경우에 한번도 안걸릴 경우 1입력

 

3. 자바 코드

import java.awt.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class P81302거리두기확인 {

	public int[] solution(String[][] places) {
		int[] answer = new int[5];
		Arrays.fill(answer, 1);
		sol(answer, places);
		return answer;
	}

	boolean sol(int[] answer, String[][] places) {
		gg:for (int idx = 0 ; idx < 5 ; idx++) {
			String [] place = places[idx];
			for (int i = 0; i < 5; i++) 
				for (int j = 0; j < 5; j++) 
					if (place[i].charAt(j) == 'P') {
						if(!check(place, i, j)) {
							answer[idx] = 0;
							continue gg;
						}
						
					}
		}
		return true;
	}

	boolean check(String[] place, int x, int y) {
		Queue<Point> que = new LinkedList<Point>();
		que.add(new Point(x, y));
		int[] dr = { 0, 0, -1, 1 };
		int[] dc = { 1, -1, 0, 0 };
		boolean visit[][] = new boolean[5][5];
		visit[x][y] = true;
		for (int cy = 0; cy < 2; cy++) {
			for (int size = que.size(); size > 0; size--) {
				Point now = que.poll();
				for (int i = 0; i < 4; i++) {
					int row = now.x + dr[i];
					int col = now.y + dc[i];
					if (row < 0 || col < 0 || row >= 5 || col >= 5 || place[row].charAt(col) == 'X')
						continue;
					if (visit[row][col])
						continue;
					if(place[row].charAt(col) == 'P')
						return false;
					visit[row][col] = true;
					que.add(new Point(row, col));
				}
			}
		}
		return true;
	}
}

4. 마치며

맵크기가 크지 않아서 같이 특정 모양의 값들을 빼와서 PP POP 모양에 대조하는 완전탐색 방법도 생각해봤는데

구현속도가 훨씬 오래 걸릴 것 같아 그냥 bfs 사용했음.