📜 문제
- 5*5 배열에
P, O, X원소가 주어짐 - P: 응시자, O: 빈 테이블, X: 파티션
BFS로 풀 수 있는 문제이다.
파티션이 응시자 사이에 있는 경우, 응시자 간 사이 거리에 무관하게 거리두기를 지킨 것으로 본다.
풀이 과정
- P, O, X를 각각 0, 1, -1로 변환하여 저장하는 2차원 tmp 배열을 선언한다.
- places 배열의 값에 따라 위와 같이 변환하여 tmp에 저장한다.
- Point 클래스를 활용해 P의 위치를 저장하는
List<Point> point변수를 선언 & 저장한다. - 대기실에 존재하는 모든 P를 시작점으로 하여 bfs를 호출한다.
POOOP
OOOPX
...
위와 같이 대기실 정보가 주어지면 (0,0)의 위치에서 거리를 계산했을 때는 통과가 되지만, (0,4)의 위치에서 거리를 계산한 경우 (1,3)에 있는 응시자와 거리두기를 지키지 않았기 때문에 모든 P에 대해서 거리를 계산한다. - 어느 한 응시자에서 거리두기가 지켜지지 않은 경우가 발견 되면 해당 대기실의 BFS를 종료하고
(0 저장), 다음 대기실을 확인한다.
✍ 부분 코드 설명
1. Point 클래스
public class Point{
int x, y;
public Point(int x, int y){
this.x = x;
this.y =y;
}
public int[] getPos(){
return new int[]{this.x, this.y};
}
}- getPos 함수는 현재 응시자의 위치를 반환한다.
2. 대기실 정보 & 응시자 위치 저장
static boolean [][] visited; // bfs 함수에서 사용
static int [][] count; // 응시자간 거리 저장
public int[] solution(String[][] places) {
int[] answer = new int[5]; // 정답 배열
int [][] tmp = new int[5][5]; // 대기실 정보 -1, 0, 1
List<Point> points = new ArrayList<>(); // 응시자 위치
for(int i=0;i<5;i++){
// i = 대기실 개수
points.clear(); // 이전 대기실 응시자 위치 초기화
for(int j=0;j<5;j++){
String str = places[i][j]; // ex) str = "POOOP"
for(int k=0; k<str.length();k++){
switch(str.charAt(k)){
case 'P':
tmp[j][k]= 0;
break;
case 'O':
tmp[j][k]= 1;
break;
case 'X':
tmp[j][k] = -1;
break;
} // switch 문 종료
if(tmp[j][k] == 0) // 응시자 위치 저장
points.add(new Point(j,k));
} // 반복문 k 종료
} // 반복문 j 종료
...- tmp 배열에 대기실 정보를 저장한다.
- points 리스트에 응시자 위치를 저장한다.
3. 저장된 정보로 bfs 호출하여 반환 값에 따라 결과 저장
...
boolean check = true;
for(int p=0;p<points.size();p++){
count = new int[5][5];
check = bfs(tmp, points.get(p));
if(!check){
answer[i] = 0; // 거리 두기를 지키지 않은 경우 0 저장
break; // 다음 point를 보지 않고 다음 대기실로 이동
}
} // 반복문 p 종료
if(check) answer[i]=1; // 거리두기가 지켜진 경우 1 저장
} // 반복문 i 종료- tmp 배열에 대기실 정보가 모두 저장되면, 응시자 별로 dfs를 호출한다.
- count 배열은 응시자 간의 거리를 저장하는 배열로, 응시자 별로 초기화 해서 사용한다.
- bfs 반환 값이 false인 경우, 0을 저장하고 즉시 다음 대기실로 이동한다.
- true인 경우, 1을 저장하고 다음 대기실로 이동한다.
4. 응시자 간 거리를 확인하는 bfs 수행
public static boolean bfs(int[][] arr, Point p){
visited = new boolean[5][5]; // 응시자 별 초기화
Queue<int[]> que = new ArrayDeque<>(); // 다음 이동 위치 저장
int [] pos = p.getPos(); // 현재 응시자 위치
que.offer(new int[]{pos[0], pos[1]});
visited[pos[0]][pos[1]] = true;
// 상하좌우 이동
int [] dx = new int[]{0,1,0,-1};
int [] dy = new int[]{1,0,-1,0};
// 더이상 이동할 곳이 없을 때까지 반복
while(!que.isEmpty()){
int[] tmp = que.poll();
for(int d=0;d<4;d++){ // 현 위치에서 상하좌우 이동
int nx = tmp[0] + dx[d];
int ny = tmp[1] + dy[d];
// 배열 범위를 벗어나지 않는 경우
if(nx>=0 && ny>=0 && nx<5&& ny<5){
// 현위치를 방문하지 않고, O 또는 P인 경우
if(!visited[nx][ny] && (arr[nx][ny]==1 || arr[nx][ny]==0)){
if(arr[nx][ny] == 1){ // O
count[nx][ny] = count[tmp[0]][tmp[1]]+1;
}
if(arr[nx][ny] == 0){ // P
count[nx][ny] = count[tmp[0]][tmp[1]]+1;
// 맨해튼 거리가 2이하인 경우
if(count[nx][ny] <=2)
return false; // false 반환 및 bfs 종료
}
visited[nx][ny]= true;
que.offer(new int[]{nx,ny});
}
}
}
}
// 현재 응시자 위치에서 다른 응시자간 거리두기를 지킴
return true;
}🍳 전체 소스 코드
import java.util.*;
class Solution {
static boolean [][] visited;
static int [][] count;
public class Point{
int x, y;
public Point(int x, int y){
this.x = x;
this.y =y;
}
public int[] getPos(){
return new int[]{this.x, this.y};
}
}
public static boolean bfs(int[][] arr, Point p){
visited = new boolean[5][5];
Queue<int[]> que = new ArrayDeque<>();
int [] pos = p.getPos();
que.offer(new int[]{pos[0], pos[1]});
visited[pos[0]][pos[1]] = true;
int [] dx = new int[]{0,1,0,-1};
int [] dy = new int[]{1,0,-1,0};
while(!que.isEmpty()){
int[] tmp = que.poll();
for(int d=0;d<4;d++){ // 현 위치에서 상하좌우 이동
int nx = tmp[0] + dx[d];
int ny = tmp[1] + dy[d];
if(nx>=0 && ny>=0 && nx<5&& ny<5){
if(!visited[nx][ny] && (arr[nx][ny]==1 || arr[nx][ny]==0)){
if(arr[nx][ny] == 1){ // O
count[nx][ny] = count[tmp[0]][tmp[1]]+1;
}
if(arr[nx][ny] == 0){ // p
count[nx][ny] = count[tmp[0]][tmp[1]]+1;
if(count[nx][ny] <=2) return false;
}
visited[nx][ny]= true;
que.offer(new int[]{nx,ny});
}
}
}
}
return true;
}
public int[] solution(String[][] places) {
int[] answer = new int[5];
int [][] tmp = new int[5][5];
List<Point> points = new ArrayList<>();
for(int i=0;i<5;i++){
points.clear();
for(int j=0;j<5;j++){
String str = places[i][j];
for(int k=0; k<str.length();k++){
switch(str.charAt(k)){
case 'P':
tmp[j][k]= 0;
break;
case 'O':
tmp[j][k]= 1;
break;
case 'X':
tmp[j][k] = -1;
break;
}
if(tmp[j][k] == 0)
points.add(new Point(j,k));
}
}
boolean check = true;
for(int p=0;p<points.size();p++){
count = new int[5][5];
check = bfs(tmp, points.get(p));
if(!check){
answer[i] = 0;
break;
}
}
if(check) answer[i]=1;
}
return answer;
}
}
✨ 결과
처음에 이상하게 접근해서 오래 걸렸다..
처음 접근 방식은 배열의 행, 열 별로 검사해서 맨해튼 거리를 만족하면 true를 반환하게 코드를 짜고 있었는데, 생각해 보니 응시자가 대각선에 있는 경우를 판단할 수 없었다.
바보 같은 접근임을 깨닫고 은근슬쩍 bfs로 했는데 맞았다.
bfs로 접근해서 처음 풀었을 때 테케의 1/3을 통과하지 못해서 당황했는데, count= new int[5][5]; 코드의 위치가 잘못됐었다.
책에는 더 효율적이고 직관적인 풀이가 있기 때문에 지금 글을 포스팅하고 난 후, 책을 읽어봐야겠다.
