문제
https://programmers.co.kr/learn/courses/30/lessons/81302
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
대기실은 5개이며, 각 대기실은 5x5 크기입니다.
거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
생각하기
앉아있는 사람인 'P'를 만날때 마다 BFS를 실행하면 풀 수 있다.
동작
int[] result = new int[places.length];
for(int i=0; i<places.length; i++) {
String[] place = places[i];
rooms = new char[5][5];
visit = new boolean[5][5];
for(int j=0; j<5; j++) {
String temp = place[j];
for(int k=0; k<5; k++) {
rooms[j][k] = temp.charAt(k);
}
}개인적으로 char형 배열로 만들어 놓고 탐색하는게 편할 것 같아서 char형 배열로 BFS탐색을 했다.
// BFS 탐색 시작
boolean check = true;
for(int k=0; k<5; k++) {
for(int l=0; l<5; l++) {
if(check == true && rooms[k][l] == 'P' && visit[k][l] == false) {
check = BFS(k, l);
}
if( check == false ) {
result[i] = 0;
break;
}
}
}BFS 탐색은 P를 만날 때 마다 해야하기때문에 일단 인접행렬 rooms를 전체를 탐색해야 한다.
check는 현재 이 대기실의 거리두기가 괜찮은지 여부를 저장하는 boolean형 변수이다.
check를 BFS의 return값으로 받아서 false일 경우, 거리두기가 지켜지지 않는다는 의미이므로, 곧바로 결과 배열에 0을 추가하도록 했다.
while( !que.isEmpty() ) {
Node node = que.poll();
for(int i=0; i<4; i++) {
nowX = dirX[i] + node.x;
nowY = dirY[i] + node.y;
nowCount = node.count;
// zero_count가 2 미만 인데 P를 만나면 곧바돌 false를 return
if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'P' && visit[nowX][nowY] == false) {
que.clear();
return false;
}
if(range_check() && nowCount > 2 && rooms[nowX][nowY] == 'P' && visit[nowX][nowY] == false) {
visit[nowX][nowY] = true;
}
if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'O' && visit[nowX][nowY] == false) {
que.offer(new Node(nowX, nowY, nowCount + 1));
visit[nowX][nowY] = true;
}
// X를 만날경우, 그냥 true처리
if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'X' && visit[nowX][nowY] == false) {
visit[nowX][nowY] = true;
}
}
}BFS 메소드는 Node형 que에 좌표값과, 거리의 값인 count를 담아 집어넣는다.
여기서는 조건이 중요한데,
char형에서 'P', 'O', 'X'의 3가지 형태가 들어가므로 적어도 3개의 조건이 필요하다고 생각했고,
예외 탈출 조건을 하나 넣어줘야겠다고 생각했다.
예외 탈출조건은 nowCount가 2 미만인데, 'P'를 만났을 경우이다.
이 조건이 거리두기가 지켜지지 않았음을 의미하므로, false를 return한다.
나머지 조건은
if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'P' && visit[nowX][nowY] == false) {
que.clear();
return false;
}nowCount가 2를 초과했는데, 'P'를 만났을 경우, 거리두기가 지켜지고 있다고 판단하고, 더 이상que에 넣지않고visit만 true를 해준다.
if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'O' && visit[nowX][nowY] == false) {
que.offer(new Node(nowX, nowY, nowCount + 1));
visit[nowX][nowY] = true;
}nowCount가 2미만 에서, 'O'를 만났을 경우이다.
이 경우는que에 넣어서 계속해서 탐색한다. 대신,que에 nowCount를 1 증가한 값을 다시 넣어준다.
// X를 만날경우, 그냥 true처리
if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'X' && visit[nowX][nowY] == false) {
visit[nowX][nowY] = true;
}nowCount가 2보다 작고, X를 만났을 경우이다.
X는 어떤경우도 괜찮기 때문에, 그냥visit만 true를 해준다.
코드
import java.util.*; class Solution { static char rooms[][]; static boolean visit[][]; static int dirX[] = {0, 0, -1, 1}; static int dirY[] = {-1, 1, 0, 0}; static int nowX, nowY, nowCount; static class Node { int x; int y; int count; public Node(int x, int y, int count) { this.x = x; this.y = y; this.count = count; } } // End of Node class public int[] solution(String[][] places) { // 결과를 담을 배열 int[] result = new int[places.length]; for(int i=0; i<places.length; i++) { String[] place = places[i]; rooms = new char[5][5]; visit = new boolean[5][5]; for(int j=0; j<5; j++) { String temp = place[j]; for(int k=0; k<5; k++) { rooms[j][k] = temp.charAt(k); } } // BFS 탐색 시작 boolean check = true; for(int k=0; k<5; k++) { for(int l=0; l<5; l++) { if(check == true && rooms[k][l] == 'P' && visit[k][l] == false) { check = BFS(k, l); } if( check == false ) { result[i] = 0; break; } } } if(check) { result[i] = 1; } } return result; } // End of solution static boolean BFS(int x, int y) { int count = 0; Queue<Node> que = new LinkedList<>(); que.offer(new Node(x, y, count)); visit[x][y] = true; while( !que.isEmpty() ) { Node node = que.poll(); for(int i=0; i<4; i++) { nowX = dirX[i] + node.x; nowY = dirY[i] + node.y; nowCount = node.count; // zero_count가 2 미만 인데 P를 만나면 곧바돌 false를 return if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'P' && visit[nowX][nowY] == false) { que.clear(); return false; } if(range_check() && nowCount > 2 && rooms[nowX][nowY] == 'P' && visit[nowX][nowY] == false) { visit[nowX][nowY] = true; } if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'O' && visit[nowX][nowY] == false) { que.offer(new Node(nowX, nowY, nowCount + 1)); visit[nowX][nowY] = true; } // X를 만날경우, 그냥 true처리 if(range_check() && nowCount < 2 && rooms[nowX][nowY] == 'X' && visit[nowX][nowY] == false) { visit[nowX][nowY] = true; } } } // 전체를 다 돌았는데도 아니면, true를 반환. return true; } // End of BFS static boolean range_check() { return (nowX >= 0 && nowX < 5 && nowY >= 0 && nowY < 5); } // End of range_check }
