[PG] 2021 카카오 채용연계 > 거리두기 확인하기
2021. 10. 10. 16:04ㆍ알고리즘/프로그래머스 문제 풀이
https://programmers.co.kr/learn/courses/30/lessons/81302
접근 방법
BFS로 간단하게 구현해주면 되는 문제이다.
주의 사항
Need Know
- BFS
전체 코드 ( Java )
import java.util.*;
class Solution {
static int[] dx = {-1,1,0,0};
static 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++){
boolean isOk = true;
loop : for(int k=0; k< 5; k++){
for(int z=0; z<5; z++){
char edge = places[i][k].charAt(z);
// 거리두기 2 이하 여야함 아니면 파티션은 ㅇㅋ
if(edge == 'P'){
boolean[][] visited = new boolean[5][5];
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(k,z,0));
visited[k][z] = true;
while(!queue.isEmpty()){
Point now = queue.poll();
for(int p = 0; p<4; p++){
int nx = now.x+dx[p];
int ny = now.y+dy[p];
if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
if(visited[nx][ny] || now.distance == 2) continue;
if(places[i][nx].charAt(ny) == 'O'){
queue.add(new Point(nx,ny,now.distance+1));
visited[nx][ny] = true;
}
if(places[i][nx].charAt(ny) == 'P'){
if(now.distance + 1 <= 2){
isOk = false;
break loop;
}
}
}
}
}
}
}
if(isOk){
answer[i] = 1;
}else{
answer[i] = 0;
}
}
return answer;
}
// }
}
class Point{
int x,y,distance;
public Point(int x, int y, int distance){
this.x = x;
this.y = y;
this.distance = distance;
}
}
'알고리즘 > 프로그래머스 문제 풀이' 카테고리의 다른 글
[PG] 카카오 블라인드 1차 테스트 > 뉴스 클러스터링 (0) | 2021.10.10 |
---|---|
[PG] 멀쩡한 사각형 (0) | 2021.10.09 |
[PG] 카카오 _ 신규 아이디 추천 (0) | 2021.09.18 |
[PG] 42890. 후보키 (0) | 2020.11.03 |
[PG] 12899. 124 숫자의 나라 (0) | 2020.10.20 |